1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| #include<bits/stdc++.h> #define pt putchar(' ') #define nl puts("") #define pi pair<int,int> #define pb push_back #define go(it) for(auto &it:as[x]) using namespace std;
const int N=4e3+10; int n,m,ans; int a[N],f[N][N][2];
int fr(){ int x=0,flag=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') flag=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ x=x*10+(ch-'0'); ch=getchar(); } return x*flag; } void fw(int x){ if(x<0) putchar('-'),x=-x; if(x>9) fw(x/10); putchar(x%10+'0'); } int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a<b?a:b;}
int main() { n=fr(),m=fr(); for(int i=1;i<=n;i++) a[i]=fr(); memset(f,-0x3f,sizeof f); f[0][0][0]=0; for(int i=1;i<=n;i++) for(int j=0;j<=min(m,i);j++) { f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]); if(j) f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+a[i]); } ans=max(f[n][m][0],f[n][m][1]); memset(f,-0x3f,sizeof f); f[1][1][1]=a[1]; for(int i=2;i<=n;i++) for(int j=0;j<=min(m,i);j++) { f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]); if(j) f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+a[i]); } ans=max(ans,f[n][m][1]); fw(ans); return 0; }
|