STEP5 0085 切木棒

[背包]

/*      LANG:CPP
**      STEP5 http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0085
**      2013-11-2
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 10000
#define max(x,y) (((x)>(y)) ? (x):(y))
int money[N+1];
int dp[2][N+1];
int main()
{
    int L;scanf("%d",&L);
    for(int lx=1;lx<=L;lx++)
        scanf("%d",&money[lx]);
    for(int lx=0;lx<=L;lx++)
        dp[0][lx]=0,dp[1][lx]=0;
    for(int lx=1;lx<=L;lx++)
    {
        for(int lm=1;lm<=L;lm++)
            if(lm<lx)
                dp[1][lm]=dp[0][lm];
            else
                dp[1][lm]=max(dp[0][lm],dp[0][lm-lx]+money[lx]);
        for(int lm=0;lm<=L;lm++)
            dp[0][lm]=dp[1][lm];
    }

    /*for(int lx=1;lx<=L;lx++)
    {
        for(int ly=1;ly<=L;ly++)
            printf("%d ",dp[lx][ly]);
        printf("\n");
    }*/
    printf("%d\n",dp[0][L]);
    return 0;
}