Solvution

件物品,每件物品有三个属性, ,
再给出个询问,每个询问由非负整数, , 组成,问是否能够选出某些物品使得:
1.对于每个选的物品,满足
2.所有选出物品的的和正好是


一开始不会做,看了Claris的代码才知道原来离线就行了。把询问按排序,每次处理一个询问就加入所有的物品。然后设为和为的物品中,最小的b值的最大值。
转移显然判断一个询问是否合法就是判断是否成立,复杂度是

Code

#include <bits/stdc++.h>
using namespace std;
#define DEBUG(...) fprintf(stderr,__VA_ARGS__)
#define IL inline
const int INF = 2147483647;
const int N = 1000 + 5 , M = 1000000 + 5 , K = 100000;
IL int read (int &res)
{
    res = 0 ; char c = getchar();
    while(!isdigit(c)) c = getchar();
    do (res *= 10) += c & 15; while(isdigit(c = getchar()));
    return res;
}
int n , q , l , L;
int dp[K + 1];
bool Ans[M];
struct Node
{
    int a , b , c;
    bool operator < (const Node &rhx) const { return a < rhx.a; }
}A[N];
struct Query
{
    int m , k , s , id;
    bool operator < (const Query &rhx) const { return m < rhx.m; }
}Q[M];
void upmax(int &x , int y){if(x < y) x = y;}
int main()
{
    read(n);
    for(int i = 1 ; i <= n ; i++ ) read(A[i].c) , read(A[i].a) , read(A[i].b);
    read(q);
    for(int i = 1 ; i <= q ; i++ ) read(Q[i].m) , read(Q[i].k) , read(Q[i].s) , Q[i].id = i , Q[i].s += Q[i].m;
    sort(A + 1 , A + 1 + n) , sort(Q + 1 , Q + 1 + q);
    dp[0] = INF;
    for(l = 1 , L = 1; l <= q ; l++ )
    {
        for( ; A[L].a <= Q[l].m && L <= n; L++ )
        {
            for(int j = K; j >= A[L].c ; j-- )
                upmax(dp[j] , min(dp[j - A[L].c] , A[L].b));
        }
        Ans[Q[l].id] = dp[Q[l].k] > Q[l].s;
    }
    for(int i = 1 ; i <= q ; i++ )
        printf("%s\n" , Ans[i] ? "TAK" : "NIE");
    return 0;
}

一开始一直以为这道题卡常数,后来发现原来是自己写残了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注