Submission

-----xxxxx

Score: 0

User: njoop

Problemset: เข้าแถว

Language: cpp

Time: 0.010 second

Submitted On: 2025-04-12 17:28:10

#include <bits/stdc++.h>
using namespace std;
int cheese[10001];
int dp[10002][102][2];
int n,g;
/*int solve(int i,int j,bool s)
{
    if(i>=n)
        return 0;
    //cout<<i<<' '<<j<<' '<<s<<'\n';
    if(dp[i][j][s]!=-1) return dp[i][j][s];
    if(s==false)
    {
        dp[i][j][s]=max(solve(i+1,j,true)+cheese[i],solve(i+1,j,false));
        if(j>0)
        {
            dp[i][j][s]=max(dp[i][j][s],solve(i+1,j-1,false)+cheese[i]);
        }
        return dp[i][j][s];
    }
    else
    {
        dp[i][j][s]=solve(i+1,j,false);
        if(j>0)
        {
            dp[i][j][s]=max(dp[i][j][s],solve(i+1,j-1,true)+cheese[i]);
        }
        return dp[i][j][s];
    }
}*/

int main()
{
    cin>>n>>g;
    /*for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=g;j++)
        {
            dp[i][j][0]=-1;
            dp[i][j][1]=-1;
        }
    }*/
    for(int i=0;i<n;i++)
    {
        cin>>cheese[i];
    }
    //0 g false
    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<=g;j++)
        {
            for(int s=0;s<2;s++)
            {
                if(s==0)
                {
                  dp[i][j][s]=max(dp[i+1][j][1]+cheese[i],dp[i+1][j][0]);
                  if(j>0)
                   {
                      dp[i][j][s]=max(dp[i][j][s],dp[i+1][j-1][0]+cheese[i]);
                   }
                }
                else
                {
                  dp[i][j][s]=dp[i+1][j][0];
                  if(j>0)
                  {
                      dp[i][j][s]=max(dp[i][j][s],dp[i+1][j-1][1]+cheese[i]);
                  }
                }
            }
        }
    }
    cout<<dp[0][g][false];
}