DP优化专题

2018-08-21

字数统计: 507字 | 阅读时长: 3min

1.优化状态

#include<cstdio>
#include<algorithm>
using namespace std;
int s[10][10],n;
int dp[10][10][10][10];
int main()
{
	scanf("%d",&n);
	int x,y,z;
	while(scanf("%d%d%d",&x,&y,&z)&&x!=0&&y!=0&&z!=0)
	{
		s[x][y]=z;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	for(int a=1;a<=n;a++)
	for(int b=1;b<=n;b++)
	{
		dp[i][j][a][b]=max(max(dp[i-1][j][a-1][b],dp[i-1][j][a][b-1]),max(dp[i][j-1][a-1][b],dp[i][j-1][a][b-1]))+s[i][j]+s[a][b];
		if(i==a&&j==b) dp[i][j][a][b]-=s[a][b];
	}
	printf("%d",dp[n][n][n][n]);
	return 0;
}

一般蒟蒻（像我）只能想到四维DP,但其实i+j==a+b,可优化状态为f[k][i][a],k==i+j==a+b.在此链接大佬博客方格取数。

乌龟棋

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int a[351];
int dp[41][41][41][41];
int c1,c2,c3,c4;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
	{
		int card;
		scanf("%d",&card);
		if(card==1) c1++;
		if(card==2) c2++;
		if(card==3) c3++;
		if(card==4) c4++;
	} 
	dp[0][0][0][0]=a[1];
	for(int i=0;i<=c1;i++)for(int j=0;j<=c2;j++)
	for(int x=0;x<=c3;x++)for(int y=0;y<=c4;y++)
	{
		if(i!=0) dp[i][j][x][y]=max(dp[i][j][x][y],dp[i-1][j][x][y]+a[i+2*j+3*x+4*y+1]);
		if(j!=0) dp[i][j][x][y]=max(dp[i][j][x][y],dp[i][j-1][x][y]+a[i+2*j+3*x+4*y+1]);
		if(x!=0) dp[i][j][x][y]=max(dp[i][j][x][y],dp[i][j][x-1][y]+a[i+2*j+3*x+4*y+1]);
		if(y!=0) dp[i][j][x][y]=max(dp[i][j][x][y],dp[i][j][x][y-1]+a[i+2*j+3*x+4*y+1]);
	}
	printf("%d",dp[c1][c2][c3][c4]);
	return 0;
}

2.数据结构优化

Bzoj2259 新型计算机

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/7236479c.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！