[DP]hdoj 4502：吉哥系列故事——临时工计划

题意：

http://acm.hdu.edu.cn/showproblem.php?pid=4502

 

大致思路：

    退役狗果然弱爆了，这么简单的转移都没想到，求bs。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int num[200][200],dp[1005];
int main(){
    int cas,i,j,n,m,a,b,c;
    cin>>cas;
    while(cas--){
        scanf("%d%d",&m,&n);
        memset(num,0,sizeof(num));
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++){
            scanf("%d%d",&a,&b);
            scanf("%d",&c);
           // scanf("%d",&num[a][b]);
            num[a][b]=max(num[a][b],c);
        }
        for(i=1;i<=m;i++){
            for(j=i;j>=1;j--){
                dp[i]=max(dp[i],dp[j-1]+num[j][i]);
            }
        }
        cout<<dp[m]<<endl;
    }
    return 0;
}