原題地址：http://codeforces.com/problemset/problem/213/C

?

題意：略

題解：dp,狀態為點的位置，直接枚舉復雜度是n4,利用兩個點坐標之和之間的關系，優化到n3。

?

#include<bits/stdc++.h>#define clr(x,y) memset((x),(y),sizeof(x))using namespace std; typedef long long LL;const int maxn=300; const int INF=1e8;int A[maxn+5][maxn+5]; int dp[maxn+5][maxn+5]; int dx[]={-1,-1,0,0}; int dx2[]={-1,0,-1,0};int n;int main(void) {#ifdef exfreopen ("../in.txt","r",stdin);//freopen ("../out.txt","w",stdout);#endifscanf("%d",&n);for (int i=1;i<=n;++i){for (int j=1;j<=n;++j){scanf("%d",&A[i][j]);}}int x1,y1,x2,y2,tmp;//cout<<dp[1][1][1]<<' '<<dp[2][1][1]<<endl;for (int i=1;i<=n;++i)for (int j=1;j<=n;++j)dp[i][j]=-INF;dp[1][1]=A[1][1];for (int i=3;i<=2*n;++i){for (int j=min(i-1,n);j>=1;--j){for (int k=min(i-1,n);k>=1;--k){int T=-INF;for (int q=0;q<=3;++q){x1=j+dx[q];x2=k+dx2[q];y1=i-1-x1;y2=i-1-x2;if (x1<=0 || x1>n || y1<=0 || y1>n) continue;if (x2<=0 || x2>n || y2<=0 || y2>n) continue;if (j==k) tmp=A[j][i-j];else tmp=A[j][i-j]+A[k][i-k];T=max(T,dp[x1][x2]+tmp);}dp[j][k]=T;//printf("%d %d %d %d\n",i,j,k,dp[j][k]); }}}int ans=dp[n][n];printf("%d\n",ans); }

?

轉載于:https://www.cnblogs.com/123-123/p/5796826.html

總結

以上是生活随笔為你收集整理的codefore 213 C Relay Race （朴素DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。