命運(yùn)

13 89 10 10 10 10 -10 10 1010 -11 -1 0 2 11 10 -20-11 -11 10 11 2 10 -10 -10 Sample Output
52 一道簡單的dp從上到下，從左到右掃一次就好了。當(dāng)前a[i][j] 的最大值取決于a[i-1][j], a[i][j-1], maxk（maxk是k倍的最大）即 a[i][j] = a[i][j] + maxthree(a[i-1][j],a[i][j-1],maxk);下面是ac代碼
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<algorithm>#include<map>#include<set>#include<queue>#include<string>#include<iostream>using namespace std;int a[23][1003];int maxthree(int a,int b,int c){	int maxs = -99999999;	if(a>maxs)	{		maxs = a;	}	if(b>maxs)	{		maxs = b;	}	if(c>maxs)	{		maxs = c;	}	return maxs;}int main(){	int zu,n,i,j,k,r,c,maxk;	scanf("%d",&zu);	while(zu--)	{		memset(a,-9999999,sizeof(a));				scanf("%d%d",&r,&c); //r行 c列		for(i=1;i<=r;i++)		{			for(j=1;j<=c;j++)			{				scanf("%d",&a[i][j]);			}		} 		a[1][0]=0;		a[0][1]=0;		for(i=1;i<=r;i++)		{			for(j=1;j<=c;j++)			{				maxk=-9999999;				for(k=2;k<=c;k++)				{					if(j%k==0&&a[i][j/k]>maxk)					{						maxk = a[i][j/k];					}				}								a[i][j] = a[i][j] + maxthree(a[i-1][j],a[i][j-1],maxk);			}		}		printf("%d/n",a[r][c]);	} 		}