AtCoder Beginner Contest 261 D - Flipping and Bonus

最近学dp，记录一下写的题
题目链接：https://atcoder.jp/contests/abc261/tasks/abc261_d

atcoder的easy场的D题，感觉和01背包有点像
D - Flipping and Bonus
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 400 points
Problem Statement
Takahashi will toss a coin N times. He also has a counter, which initially shows 0.
Depending on the result of the i-th coin toss, the following happens:
If it heads: Takahashi increases the counter’s value by 1 and receives Xi yen (Japanese currency).If it tails: he resets the counter’s value to 0, without receiving money.
Additionally, there are M kinds of streak bonuses. The i-th kind of streak bonus awards Yi yen each time the counter shows C i

Find the maximum amount of money that Takahashi can receive.

题目大意：初始分数为0，投n次硬币：第 i 次若正面朝上，则分数+1，并获得相应的Xi 的价值 ，若反面朝上，则分数清零 不获得任何价值。
对于每一次正面朝上的情景，若当前分数为C i，则可以额外获得对应的Y i的价值，该价值可以多次获得
数据范围：
Constraints
1≤M≤N≤5000
1≤X i ≤10^9
1≤C i ≤N
1≤Yi≤10^9
C1 ,C 2 ,…,CM are all different.
All values in input are integers.

n的范围是5e3 ，考虑二维dp
dp[i][j]表示已经投了i个硬币，当前得分为j可能获得的最大价值
最终答案取dp[n][0]到dp[n][n]中的最大值就可以了

开两个数组，分别存储Xi和Ci (下标为当前得分，对应的值就是可以额外获得的价值)
dp的状态转移方程：
当 j>0 时 显然*

dp[i][j]=dp[i-1][j-1]+x[i]+c[j];

*因为只有第i次正面朝上才能大于0，而正面朝上会加一分，所以是由dp[i-1][j-1]转移过来的 ，x[i]和c[j]就是该轮获得的相应价值
而当j＝0时 dp[i][j]可能由小于i-1的任何一个分数转移过来 ，因为i-1轮最多就是i-1分，最小可能是0分,所以

dp[i][0]=max(dp[i-1][0],dp[i-1][1],…dp[i-1][i-1])

当j=0的时候需要逐个枚举，但是其他情况都是直接转移，故算法时间复杂度还是O(n^2)
注意整数可能溢出要开long long
code:

#include <iostream>
using namespace std;
 
 
#define int long long
#define endl "\n"
 
const int N=5e3+50;
 
int dp[N][N],c[N],x[N];
int n,m;
//dp[i][j]表示投了i个硬币，当前得分为j可以获得的最大价值
 
signed main()
{
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>x[i];
    while(m--){
    
        int xx,yy;
        cin>>xx>>yy;
        c[xx]=yy;
    }
    for(int i=1;i<=n;++i){
    
        for(int j=0;j<=n;++j){
    
            if(j)dp[i][j]=dp[i-1][j-1]+x[i]+c[j];
            else {
    
                int t=-1;
                for(int k=0;k<i;++k){
    
                    t=max(t,dp[i-1][k]);
                }
                dp[i][j]=t;
            }
        }
    }
    int ans=dp[n][0];
    for(int i=1;i<=n;++i)ans=max(ans,dp[n][i]);
    cout<<ans<<endl;
    return 0;
}