Codeforces Round #131 (Div. 2) 完整题解

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

第一次进入DIV1，果断被虐，没法下手。赛后先把DIV2解决了吧

A. System of Equations

问a*a+b=m a+b*b=n，的解a,b,有多少组，因为a,b都非负，而且m和n的范围在1000以内，直接暴力，1000*1000即可

#include<iostream>#include<cstring>#include<queue>#include<cstdio>#include<cmath>#include<algorithm>#define N 305#define inf 1<<29#define MOD 9973#define Max 301#define LL long long#define eps 1e-7#define zero(a) fabs(a)<eps#define equal(a,b) zero(a-b)using namespace std;int dp[N<<1][N][N];int a[N][N],n;int way[4][2]={{0,0},{0,1},{1,0},{1,1}};int main(){while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)    scanf("%d",&a[i][j]);memset(dp,0x81,sizeof(dp));dp[0][1][1]=a[1][1];for(int i=1;i<=2*n-2;i++)for(int j=1;j<=i+1&&j<=n;j++)for(int k=j;k<=i+1&&k<=n;k++){for(int r=0;r<4;r++)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-way[r][0]][k-way[r][1]]);dp[i][j][k]+=a[j][i-j+2]+a[k][i-k+2]-(j==k?a[k][i-k+2]:0);}printf("%d\n",dp[2*n-2][n][n]);}return 0;}