NC16496（飞扬的小鸟 ）

感受



思路

for(int q = max(0, m - x[i - 1]); q <= m; q++){
   dp[i][m] = min(dp[i][m], min(dp[i][q] + 1, dp[i - 1][q] + 1));
}

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int n, m, k;
int x[maxn], y[maxn];
struct node{
    int l, r;
}a[maxn];
priority_queue<int> que;
bool mp[maxn];
int dp[maxn][1010];
void print(){
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            if(dp[i][j] == inf) printf("? ");
            else printf("%d ", dp[i][j]);
        }
        putchar('\n');
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < n; i++){
        scanf("%d%d", &x[i], &y[i]);
    }
    int id;
    for(int i = 1; i <= k; i++){
        scanf("%d", &id); scanf("%d%d", &a[id].l, &a[id].r);
        que.push(id); mp[id] = true;
    }
    memset(dp, 0x3f, sizeof(dp));
    for(int j = 1; j <= m; j++) dp[0][j] = 0;
    for(int i = 1, j, l, r; i <= n; i++){
        l = 1; r = m;
        if(mp[i]) l = a[i].l + 1, r = a[i].r - 1;
        for(j = 1; j <= m; j++){
            if(j >= x[i - 1]) dp[i][j] = min(dp[i][j], min(dp[i - 1][j - x[i - 1]], dp[i][j - x[i - 1]]) + 1);
        }
        if(r == m){
            for(int q = max(0, m - x[i - 1]); q <= m; q++){
                dp[i][m] = min(dp[i][m], min(dp[i][q] + 1, dp[i - 1][q] + 1));
            }
        }//先枚举点击
        for(j = 1; j <= m; j++){
            if(j + y[i - 1] <= m) dp[i][j] = min(dp[i][j], dp[i - 1][j + y[i - 1]]);
        }//再枚举不点击
        for(j = 1; j < l; j++) dp[i][j] = inf;
        for(j = r + 1; j <= m; j++) dp[i][j] = inf;
    }
    //print();
    int ans = inf; int use = 0;
    for(int j = 1; j <= m; j++){
        ans = min(ans, dp[n][j]);
    }
    while(!que.empty()){
        bool is = false;
        int id = que.top();
        for(int j = 1; j <= m; j++){
            if(dp[id][j] != inf){
                is = true;
                break;
            }
        }
        if(is) break;
        que.pop();
        use++;
    }
    if(ans != inf){
        printf("1\n%d\n", ans);
    }
    else{
        printf("0\n%d\n", k - use);
    }
    return 0;
}
/*
3 8 3
5 4
1 6
6 7
1 1 4
2 5 7
3 3 8

0
2
*/