四维动态规划

KaQqi

四维dp
题目：
https://www.luogu.org/problemnew/show/P1004

代码：

[C++] 纯文本查看 复制代码

#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[10][10];//用于储存输入的数组
        int dp[10][10][10][10];//dp数组用于记录两个人从a走到这的最大值
        for(int i = 0;i<10;i++)//初始化数组
        {
                for (int j = 0;j<10;j++)
                {
                        data[i][j] = 0;
                        for(int k=0;k<10;k++)
                        {
                                for (int l = 0;l<10;l++)
                                {
                                        dp[i][j][k][l] = 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[horizontal][vertical] = 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[i][j][k][l]=calculateMax(dp[i-1][j][k-1][l],dp[i][j-1][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k][l-1])+data[i][j];
                                                continue;
                                        }
                                        dp[i][j][k][l]=calculateMax(dp[i-1][j][k-1][l],dp[i][j-1][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k][l-1])+data[i][j]+data[k][l];
                                        
                                }
                        }
                }
        }
        printf("%d",dp[n][n][n][n]);
        return 0;
}

P1006跟这道题有点像，也是四维dp。。
https://www.luogu.org/problemnew/show/P1006

[Asm] 纯文本查看 复制代码

#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[51][51];
int dp[51][51][51][51];//两条路的好心程度大小
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[i][j]);
		}
	}
	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[i][j][i][j] = calculateMax(dp[i-1][j][k-1][l],dp[i][j-1][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k][l-1])+data[i][j];
						continue;
					}
					dp[i][j][k][l]=calculateMax(dp[i-1][j][k-1][l],dp[i][j-1][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k][l-1])+data[i][j]+data[k][l];	
				}
			}
		}
	}
	printf("%d",dp[m][n][m][n]);
	return 0;
}

Ps:dp好难理解，还是用我大dfs的枚举好

quaternion

这是什么  能详细说下吗？

苏紫方璇

一脸懵逼的进来，一脸懵逼的出去，

KaQqi

苏紫方璇 发表于 2019-5-4 16:54
一脸懵逼的进来，一脸懵逼的出去，

毕竟szfx大神不搞acm嘛