P1005矩阵取数游戏——求救
查看原帖
P1005矩阵取数游戏——求救
509794
快乐的小男生楼主2021/10/13 19:45

矩阵取数游戏,求哪位大佬给我这个蒟蒻指明错误(该代码50分,wa了5个点)

#include<cstdio>
#include<cstring>
using namespace std;
__int128 n,m,sn;
__int128 f[83][83],v[83];
__int128 pow2[83];
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;
}
inline void print(__int128 x)
{
    if(x<0)
	{
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
inline __int128 max(__int128 x,__int128 y)
{
	if(x>y)
		return x;
	return y;
}
inline __int128 dpfs(int day,int l,int r)
{
	if(r<1 || l>m)
		return 0;
	if(f[l][r]!=0)
		return f[l][r];
	f[l][r]=max(dpfs(day+1,l+1,r)+pow2[day]*v[l],dpfs(day+1,l,r-1)+pow2[day]*v[r]);
	return f[l][r];	
}
int main()
{
	__int128 a=1;
	for(register int i=1;i<=80;++i) 
	{
		a=a*2;
		pow2[i]=a;
	}
	n=read();m=read();
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=m;++j)
		{
			v[j]=read();
			f[j][j]=v[j]*pow2[m];
		}
		dpfs(1,1,m);
		sn+=f[1][m];
		memset(f,0,sizeof(f));
	}
	print(sn);
	return 0;
}
2021/10/13 19:45
加载中...