萌新求助区间dp,只有60分WA
查看原帖
萌新求助区间dp,只有60分WA
294736
bovine__kebi楼主2020/7/13 21:18

RT,看不出来哪里错了(禁止wyy回复)

#include<bits/stdc++.h>
using namespace std;
const int Inf=99999999;
const int maxn=105;
int a[maxn];
int maxx=-Inf,minn=Inf;
int dp1[maxn][maxn][maxn];
int dp2[maxn][maxn][maxn];
int S[maxn];
inline int Orz(int n)
{
    return ((n%10)+10)%10;
}
int main()
{
    int n,m;scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i];
    for(int i=1;i<=2*n;i++)S[i]=S[i-1]+a[i];
	memset(dp2,0x3f,sizeof(dp2));
	for(int i=2;i<=m;i++)
	{
		for(int j=1;i<=2*n;i++)
		{
			for(int k=j+i-1;k<=2*n;k++)
			{
				dp2[j][k][i]=Inf;
			}
		}
	}
    for(int i=1;i<=2*n;i++)
    {
        for(int j=i;j<=2*n;j++)
        {
            dp1[i][j][1]=dp2[i][j][1]=Orz(S[j]-S[i-1]);
        }
    }
    for(int k=2;k<=m;k++)
    {
        for(int len=1;len<=2*n-1;len++)
        {
            for(int i=1;i<=2*n-len;i++)
            {
                int j=i+len;
                for(int p=i;p<=j-1;p++)
                {
                    dp1[i][j][k]=max(dp1[i][j][k],dp1[i][p][k-1]*dp1[p+1][j][1]);
                    dp2[i][j][k]=min(dp2[i][j][k],dp2[i][p][k-1]*dp2[p+1][j][1]);
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        maxx=max(maxx,dp1[i][i+n-1][m]);
        minn=min(minn,dp2[i][i+n-1][m]);
    }
    printf("%d\n%d\n",minn,maxx);
}
2020/7/13 21:18
加载中...