方格取数问题_邓文皓的博客-爱代码爱编程
方格取数问题是关于一个矩阵,每个位置都有相应的权值从左上角走到右下角俩次,问你最大的得分
活动 - AcWing 本课程系统讲解常用算法与数据结构的应用方式与技巧。https://www.acwing.com/problem/content/1029/这道题是每个位置的权值大于等于0,运用y总的方法
#include<iostream>
using namespace std;
const int N=15;
int w[N][N];
int f[2*N][N][N];
int n;
int main()
{
cin>>n;
int i,j,k;
while(cin>>i>>j>>k,i||j||k)
{
w[i][j]=k;
}
for(i=2;i<=2*n;i++)
{
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
{
int j1=i-j;
int k1=i-k;
if(j1>=1&&j1<=n&&k1>=1&&k1<=n)
{
int t=w[j][j1];
if(j1!=k1)t+=w[k][k1];
int& v=f[i][j][k];
v=max(v,f[i-1][j-1][k-1]+t);
v=max(v,f[i-1][j-1][k]+t);
v=max(v,f[i-1][j][k-1]+t);
v=max(v,f[i-1][j][k]+t);
}
}
}
cout<<f[2*n][n][n]<<endl;
return 0;
}
在这道题权值非负数的时候是正确的,但是当我们题目的权值不是负数时,就出现了问题
这道题的权值包含负数,y总的方法就会存在不适用的情况,洛谷在这道题上有人写出了增强版,可以应对负数的情况,当然,这道题要是不含有负数,运用费用流也是可以做的,尽管点数多了一点,但是问题不大
#include<iostream>
#include<cstring>
using namespace std;
const int N=15;
int w[N][N];
int f[2*N][N][N];
int n;
int main()
{
cin>>n;
int i,j,k;
while(cin>>i>>j>>k,i||j||k)
{
w[i][j]=k;
}
memset(f,-0x3f,sizeof(f));
f[1][1][1]=w[1][1];
for(i=2;i<=2*n-1;i++)
{
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
{
int j1=i-j+1;
int k1=i-k+1;
if(j1>=1&&j1<=n&&k1>=1&&k1<=n)
{
int t=w[j][j1];
if(j1!=k1)t+=w[k][k1];
int& v=f[i][j][k];
v=max(v,f[i-1][j-1][k-1]+t);
v=max(v,f[i-1][j-1][k]+t);
v=max(v,f[i-1][j][k-1]+t);
v=max(v,f[i-1][j][k]+t);
}
}
}
cout<<f[2*n-1][n][n]<<endl;
return 0;
}