程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDOJ4502 吉哥系列故事——臨時工計劃(動態規劃)&& 騰訊2013編程馬拉松第0

HDOJ4502 吉哥系列故事——臨時工計劃(動態規劃)&& 騰訊2013編程馬拉松第0

編輯:C++入門知識

先讀取,篩選出符合條件的工作(如超過了規定時長的去掉)

建立二維數組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;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved