Description

Solution

显然的区间DP，正常想法f[i][j]表示前i个数分成j块，每次在i前找一个k使得balala，然而常规打法会超时

我们发现，对于i前面的所有点，他们的值在[0,p)之间，而有些f[k][j-1]的值是相同的，而他们的贡献也是一样的，

所以直接枚举[0,p)即可，

然后可以进一步优化空间，f[i][j]表示膜p为i分为j块的最大价值

Code

#include 
     
      #include 
      
       #include 
       
        using namespace std;int n,m,mo,s[20010],f[110][60],g[60];inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int main(){    n=read(),m=read(),mo=read();    for(int i=1;i<=n;++i) s[i]=(s[i-1]+read())%mo;    memset(f,128,sizeof(f));    f[0][0]=0;    for(int i=1;i<=n;++i){    	memset(g,128,sizeof(g));		for(int j=1;j<=m;++j)			for(int k=0;k