AcWing 1027. 方格取数
原题链接
简单
作者:
Eva_0
,
2021-01-29 17:35:50
,
所有人可见
,
阅读 324
几维就需要几层循环,没一个维度均需要遍历
扩大维度实则在乘平方
正常二维是只需要横坐标,纵坐标,两个数确定一个小方块的值,有n²个小方块
现在变成四维后,需要用四个数来确定一个小方块的位置,有n的四次方个小方块
没一个小方块分为从[i1][j1]上面,右面两种情况 [i2][j2]上面右面两种情况
所以2*2等于四,所以每一个小方块是从这四种中取最大值,作为该位置小方块的值
算法1
(暴力枚举)
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int arr[N][N];
int dp[N][N][N][N];
int main()
{
int n;
cin>>n;
int l,r,c;
cin>>l>>r>>c;
while(l!=0&&r!=0&&c!=0)
{
arr[l][r]=c;
cin>>l>>r>>c;
}
for(int i1=1;i1<=n;i1++)
{
for(int j1=1;j1<=n;j1++)
{
for(int i2=1;i2<=n;i2++)
{
for(int j2=1;j2<=n;j2++)
{
int t=arr[i1][j1];
if(i1!=i2&&j1!=j2)t+=arr[i2][j2];
int x=dp[i1][j1][i2][j2];
x=max(x,dp[i1-1][j1][i2-1][j2]+t);
x=max(x,dp[i1-1][j1][i2][j2-1]+t);
x=max(x,dp[i1][j1-1][i2-1][j2]+t);
x=max(x,dp[i1][j1-1][i2][j2-1]+t);
dp[i1][j1][i2][j2]=x;
}
}
}
}
cout<<dp[n][n][n][n];
return 0;
}
进阶版(四维度降三维)
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int arr[N][N];
int dp[N*2][N][N];
int main()
{
int n;
cin>>n;
int l,r,c;
cin>>l>>r>>c;
while(l!=0&&r!=0&&c!=0)
{
arr[l][r]=c;
cin>>l>>r>>c;
}
for(int k=2;k<=n*2;k++)
{
for(int i1=1;i1<=k;i1++)
{
for(int i2=1;i2<=k;i2++)
{
int j1=k-i1;
int j2=k-i2;
if(j1>=1&&j1<=n&&j2>=1&&j2<=n)
{
int t=arr[i1][j1];
if(i1!=i2)t+=arr[i2][j2];
dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2]+t);
dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2-1]+t);
dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2]+t);
dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2-1]+t);
}
}
}
}
cout<<dp[n*2][n][n];
return 0;
}