HDOJ4502 吉哥系列故事——临时工计划(动态规划）&& 腾讯2013编程马拉松第0场第三题
先读取，筛选出符合条件的工作（如超过了规定时长的去掉）
建立二维数组dp[][]，dp[i][j]表示第i天到第j天的最大收益
显然，可以得到一条状态转移方程
对于一个工作，时间为a到b，它的收益是w，那么有：
dp[i][j]=max(dp[i][j],dp[i][a-1]+dp[b+1][j]+w);
[cpp]
/*HDOJ4502 && 腾讯2013编程马拉松第0场第三题
作者：陈佳润
2013-04-14
*/
#include<iostream>
using namespace std;
int dp[105][105];
int m;
void z(int a,int b,int c){//动态规划
int i,j;
for(i=0;i<=a;i++)
for(j=m;j>=b;j--)
{
if(dp[i][j]<dp[i][a-1]+dp[b+1][j]+c)
dp[i][j]=dp[i][a-1]+dp[b+1][j]+c;
}
}
int main(){
int Time,n,k,i,a,b,c,va[1005],vb[1005],vc[1005];
//freopen("1.txt","r",stdin);
scanf("%d",&Time);
while(Time--){
scanf("%d%d",&m,&n);
k=0;
for(i=1;i<=n;i++){
scanf("%d%d%d",&a,&b,&c);
if(a>0&&a<=m&&b>0&&b<=m)//筛选出符合条件的工作
{
k++;
va[k]=a;
vb[k]=b;
vc[k]=c;
}
}
memset(dp,0,sizeof(dp));
for(i=1;i<=k;i++){//动态规划
z(va[i],vb[i],vc[i]);
}
cout<<dp[1][m]<<endl;
}
return 0;
}
/*HDOJ4502 && 腾讯2013编程马拉松第0场第三题
作者：陈佳润
2013-04-14
*/
#include<iostream>
using namespace std;
int dp[105][105];
int m;
void z(int a,int b,int c){//动态规划
int i,j;
for(i=0;i<=a;i++)
for(j=m;j>=b;j--)
{
if(dp[i][j]<dp[i][a-1]+dp[b+1][j]+c)
dp[i][j]=dp[i][a-1]+dp[b+1][j]+c;
}
}
int main(){
int Time,n,k,i,a,b,c,va[1005],vb[1005],vc[1005];
//freopen("1.txt","r",stdin);
scanf("%d",&Time);
while(Time--){
scanf("%d%d",&m,&n);
k=0;
for(i=1;i<=n;i++){
scanf("%d%d%d",&a,&b,&c);
if(a>0&&a<=m&&b>0&&b<=m)//筛选出符合条件的工作
{
k++;
va[k]=a;
vb[k]=b;
vc[k]=c;
}
}
memset(dp,0,sizeof(dp));
for(i=1;i<=k;i++){//动态规划
z(va[i],vb[i],vc[i]);
}
cout<<dp[1][m]<<endl;
}
return 0;
}
补充：软件开发 , C++ ,
