FZU2234 牧场物语 DP

题意:先去再回,不能吃重复的,获取最大值

分析:等价于两个人同时去,不能吃重复的

定义dp[i][j][k]表示从起点走k步,第一个人的横坐标是i,第二个人的横坐标是j的最最大值

这个题和bc上一个回文串的题是一样的

#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
const int N=1e2+;
const int INF=0x3f3f3f3f;
int n;
LL dp[N][N][N*];
LL a[N][N];
int dx[]= {,-};
int dy[]= {-,};
int main()
{
while(~scanf("%d",&n))
{
for(int i=; i<=n; ++i)
for(int j=; j<=n; ++j)
scanf("%I64d",&a[i][j]);
dp[][][]=a[][];
for(int k=; k<=*n-; ++k)
{
for(int i=; i<=n; ++i)
{
for(int j=; j<=n; ++j)
{
int x1=i,y1=k-i+,x2=j,y2=k-j+;
if(y1<||y1>n||y2<||y2>n)continue;
LL tmp=a[x1][y1]+a[x2][y2];
if(x1==x2&&y1==y2)tmp-=a[x1][y1];
bool flag=;
for(int k1=; k1<; ++k1)
{
for(int k2=; k2<; ++k2)
{
if(x1+dx[k1]<||y1+dy[k1]<)continue;
if(x2+dx[k2]<||y2+dy[k2]<)continue;
int k3=x1+dx[k1],k4=x2+dx[k2];
if(flag)dp[i][j][k]=dp[k3][k4][k-]+tmp,flag=;
else dp[i][j][k]=max(dp[i][j][k],dp[k3][k4][k-]+tmp);
}
}
}
}
}
printf("%I64d\n",dp[n][n][*n-]);
}
return ;
}
上一篇:Insight API开源项目介绍


下一篇:USDT