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

题意 :这个是中文题,我就不再详述了。

思路 : 以前做过一个活动区间选择,结果就按着那个思路敲了,后来发现只能保证做足够多的工作,但是无法保证获得的钱最多,才知道是一个动态规划,其实对于我这种菜鸟来说,做动态规划没有什么难不难的,只有找不找的到公式的。。。。。我的代码里dp[h][k]代表的是从第h天干到第k天能赚多少钱,所以存在一个变量h < j < k,就是从第h天干到第 j 天的前一天,再从第 j 天结束后的那天开始干到第 k 天,再加上这 j 天干的得到的工资,应该不难理解。

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<algorithm>
using namespace std ;
struct node
{
int start ;
int end ;
int sac ;
} ch[] ;
int dp[][] ;
int main()
{
int n ;
scanf("%d",&n) ;
for(int i = ; i < n ; i++)
{
int a,b ;
scanf("%d %d",&a,&b) ;
for(int j = ; j < b ; j++)
{
scanf("%d %d %d",&ch[j].start,&ch[j].end,&ch[j].sac);
} memset(dp,,sizeof(dp)) ;
for(int j = ; j < b ; j++)
{
if(ch[j].end <= a){ for(int h = ; h <= ch[j].start ; h++)
for(int k = a ; k >= ch[j].end ; k--)
if(dp[h][k] < dp[h][ch[j].start-]+dp[ch[j].end+][k]+ch[j].sac)
dp[h][k] = dp[h][ch[j].start-]+dp[ch[j].end+][k]+ch[j].sac;
}
}
printf("%d\n",dp[][a]) ;
}
return ;
}
05-08 08:34