HDU 1574 RP问题

省赛明天就选拔了，人品有木有。这个题的意思就是你干好事的时候呢，人品值是上升的+a，但是必须是你的当前人品要低于或者等于b的值，然后你的获益是+c。反之就全都是反着的。然后呢，由于题目的变量的范围以及可能出现负人品的情况，所以初始的值+10000，也就是初始值是10000。然后我们设置一个visited数组记录这个人品值有没有可能达到。当然最后的结果得总的遍历一遍，嘿，竟然不超时。

贴上代码，解释下面附上。

#include<iostream>using namespace std;int dp[20010];int visited[20010];int maxi(int a,int b){if(a>b)return a;else return b;}int main(){int T,N,a,b,c,j,i;cin>>T;while(T!=0){cin>>N;memset(dp,0,sizeof(dp));memset(visited,0,sizeof(visited));visited[10000]=1;while(N!=0){cin>>a>>b>>c;b=b+10000;if(a>0){for(j=b;j>=0;j--){if(visited[j]==1)//j这个人品值必须要有，所以先判断一下{if(visited[j+a]==0){//如果这个人品值当前没有，那就直接修改，别忘了visited数组也要修改。                                dp[j+a]=dp[j]+c;visited[j+a]=1;}else {//如果这个人品值得值已经有啦，怎么去这个值你懂的。

    dp[j+a]=maxi(dp[j+a],dp[j]+c);}}}}if(a<0){for(j=b;j<20010;j++){if(visited[j]==1){if(visited[j+a]==0){dp[j+a]=dp[j]+c;visited[j+a]=1;}else{dp[j+a]=maxi(dp[j+a],dp[j]+c);}}}}N=N-1;}int ans=0;for(i=0;i<20010;i++){if(visited[i]==1&&ans<dp[i])ans=dp[i];}cout<<ans<<endl;T=T-1;}return 0;}