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
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][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< }
return 0;
}

/*HDOJ4502 && 腾讯2013编程马拉松第0场第三题
作者：陈佳润
2013-04-14
*/
#include
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][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< }
return 0;
}