codeforces455A Boredom (裸DP)

codeforces455A Boredom (裸DP)

題意：

從n個數中選出一個數 x,得到x的獎勵，但是要去掉所有值為x-1和x+1的數，當所有的數都取光的時候求得到最大的獎勵

分析：

很裸的一個DP

dp[i]=max(dp[i-1],dp[i-2]+num[i]*i) 表示取值為i的時候所能得到的最大獎勵。

代碼如下：

#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int maxn = 500010;

int num[maxn];
LL dp[maxn];

int main()
{
    int n;
    while(~scanf(%d,&n)){
        memset(num,0,sizeof(num));
        memset(dp,0,sizeof(dp));
        int mmax=0,x;
        for(int i=0;immax) mmax=x;
        }
        dp[1]=num[1];
        for(int i=2;i<=mmax;i++)
            dp[i]=max(dp[i-1],dp[i-2]+(LL)i*num[i]);
        printf(%lld
,dp[mmax]);
    }
    return 0;
}