【DP】Codeforces 958C2 Encryption (medium)

一道简单的DP题……

题面在这里

\(f_{i,j,k}\)表示前i个元素分为j部分,最后一块值为k

对于第i个元素,讨论它在前一块还是后一块就好了

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=20005;
int n,K,p,a[maxn];
int f[maxn][55][105],dp[maxn][55];
int main(){
scanf("%d%d%d",&n,&K,&p);
for (int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]%=p;
memset(f,0xc0,sizeof(f));
memset(dp,0xc0,sizeof(dp));
f[0][0][0]=0;dp[0][0]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=K&&j<=i;j++){
f[i][j][a[i]]=max(f[i-1][j][0]+a[i],dp[i-1][j-1]+a[i]);
for (int m=1;m<p;m++)
f[i][j][(a[i]+m)%p]=max(f[i][j][(a[i]+m)%p],f[i-1][j][m]-m+(a[i]+m)%p);
for (int k=0;k<p;k++) dp[i][j]=max(dp[i][j],f[i][j][k]);
}
printf("%d",dp[n][K]);
return 0;
}