[POI 19 Stage 2] Cloakroom

作法：

首先把問題轉換成：給定一些線段，每條線段有他自己的價值，每次詢問一個區間，問在所有包含這個區間的線段中能不能用他們的價值湊出給定的價值。

假設現在的詢問是 [ L , R ] ，問能不能湊出 C ，那麼可以發現：如果詢問的 R 值變得越來越小，會讓可以湊出 C 的可能性越來越高(因為有更多的線段包含了詢問的區間)，所以我們可以對一個價值 C 只記錄他的臨界點，代表詢問的區間右端點 <= 這個臨界點的時候是有辦法湊出 C 的，否則就是沒辦法。所以我們考慮離線處理所有詢問，按照詢問的左端點由小到大排序，每次作下一個詢問的時候，先把所有線段左端點 <= L 的線段拿去更新剛才的臨界點陣列，然後直接查詢詢問價值的臨界點是否 >= 詢問的區間右端點即可。


code :

#include<bits/stdc++.h>
#define INF 1100000000
using namespace std;
const int maxn=1000+10 , maxq=1000000+10 , maxc=100000+10 ;
 
struct P
{
    int l,r,c,id;
    bool operator < (const P &rhs) const
    {
        return l==rhs.l ? r<rhs.r : l<rhs.l ;
    }
}a[maxn],q[maxq] ;
 
int dp[maxc] ;
bool ans[maxq] ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].c,&a[i].l,&a[i].r) ;
    int Q ; scanf("%d",&Q) ;
    for(int i=1;i<=Q;i++)
        scanf("%d%d%d",&q[i].l,&q[i].c,&q[i].r) ,
        q[i].id=i ,
        q[i].r+=q[i].l+1 ;
 
    sort(a+1,a+n+1) ; sort(q+1,q+Q+1) ;
    dp[0]=INF ;
    for(int i=1,j=1;i<=Q;i++)
    {
        while(j<=n && a[j].l <= q[i].l)
        {
            for(int k=maxc-1;k>=a[j].c;k--)
                dp[k]=max(dp[k],min(dp[k-a[j].c],a[j].r)) ;
            j++ ;
        }
        ans[q[i].id]= (q[i].r<=dp[q[i].c] ? 1 : 0) ;
    }
    for(int i=1;i<=Q;i++) printf("%s\n",ans[i]?"TAK":"NIE") ;
}