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;
}