四维动态规划
本帖最后由 KaQqi 于 2019-5-4 16:14 编辑四维dp
题目：
https://www.luogu.org/problemnew/show/P1004
代码：#include <stdio.h>
int calculateMax(int a,int b,int c,int d)
{
if(a>=b && a>=c && a>=d) return a;
if(b>=a && b>=c && b>=d) return b;
if(c>=b && c>=a && c>=d) return c;
if(d>=b && d>=c && d>=a) return d;
}
int main()
{
int n;
int data;//用于储存输入的数组
int dp;//dp数组用于记录两个人从a走到这的最大值
for(int i = 0;i<10;i++)//初始化数组
{
for (int j = 0;j<10;j++)
{
data = 0;
for(int k=0;k<10;k++)
{
for (int l = 0;l<10;l++)
{
dp = 0;
}
}
}
}
scanf("%d",&n);
while(1)//输入
{
int horizontal;
int vertical;
int num;
scanf("%d%d%d",&horizontal,&vertical,&num);
if(horizontal == 0&&vertical==0&&num==0) break;
data = num;
}
for(int i=1;i<=n;i++)//第一个人
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)//第二个人
{
for(int l=1;l<=n;l++)
{
if(i==k&&j==l)//如果两个人路径一样，那么就只加一个人的就行了
{
dp=calculateMax(dp,dp,dp,dp)+data;
continue;
}
dp=calculateMax(dp,dp,dp,dp)+data+data;
}
}
}
}
printf("%d",dp);
return 0;
}
P1006跟这道题有点像，也是四维dp。。
https://www.luogu.org/problemnew/show/P1006
#include <stdio.h>
int calculateMax(int a,int b,int c,int d)
{
if(a>=b && a>=c && a>=d) return a;
if(b>=a && b>=c && b>=d) return b;
if(c>=b && c>=a && c>=d) return c;
if(d>=b && d>=c && d>=a) return d;
}
int data;
int dp;//两条路的好心程度大小
int main()
{
int m,n;
scanf("%d %d",&m,&n);
for(int i = 1;i<=m;i++)
{
for (int j = 1;j<=n;j++)
{
scanf("%d",&data);
}
}
for(int i = 1;i<=m;i++)
{
for (int j = 1;j<=n;j++)
{
for (int k = 1;k<=m;k++)
{
for (int l = 1;l<=n;l++)
{
if(i == k && j == l)
{
dp = calculateMax(dp,dp,dp,dp)+data;
continue;
}
dp=calculateMax(dp,dp,dp,dp)+data+data;
}
}
}
}
printf("%d",dp);
return 0;
}
Ps:dp好难理解，还是用我大dfs的枚举好 这是什么能详细说下吗？
一脸懵逼的进来，一脸懵逼的出去，{:1_925:} 苏紫方璇 发表于 2019-5-4 16:54
一脸懵逼的进来，一脸懵逼的出去，
毕竟szfx大神不搞acm嘛
页:
[1]