wen 编程最新 2024-01-26

P1005 [NOIP2007 提高组] 矩阵取数游戏

题目传送门

前言

今天依旧是不写高精的一天呢！（是的，这位作者又只拿了开 (LL) 的 (color{yellow}{60}) 分）

思路描述

看到数据 (n,m le 80(30)) 就知道数组可以任性开，心理有个底后，再来看题目。

状态描述

首先肯定要来一个 (dp_{i,j}) 来表示第 (i) 次时取第 (j) 行的数。

对于每一次放置，我们要考虑到的是之前每一次都取到什么,也就是现在的头和尾分别是哪两个数。

想明白这一点，就可以描述状态了。

(dp_{i,j,k,t}) 表示第 (i) 次时取第 (j) 行的数，对于第 (j) 行，它的行首被取了 (k) 个数，他的行尾被取了 (t) 个数。

由于 $t = i – k $ ，当 (i，k) 确定时，(t) 也一定唯一，因此可以省略。

状态转移方程

描述出状态了，状态转移方程还会远吗？

显然有

(dp_{i,j,k} = max(dp_{i-1,j,k-1}+val（i,j,k）,dp_{i-1,j,k}+val(i,j,m-(i-k)+1)))。

(val(x,y,z)) 表示第 (x) 次时取位于第 (y) 行第 (z) 列的数所能获得的得分。

(max) 中的两者分别对应了第 (i) 次时，在第 (j) 行取队首 (or) 队尾的情况。

code

点击查看代码

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int n,m;
ll a[85][85],dp[85][85][85];
int bas[31];
int main(){
	scanf("%d%d",&n,&m);
	bas[0]=1;
	for(int i=1;i<=30;i++) bas[i]=bas[i-1]*2;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
		
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			dp[i][j][i]=dp[i-1][j][i-1]+a[j][i]*bas[i],dp[i][j][0]=dp[i-1][j][0]+a[j][m-i+1]*bas[i];//这两种情况比较特殊，所以单独列。
			for(int k=1;k<i;k++){
				dp[i][j][k]=max(dp[i-1][j][k-1]+a[j][k]*bas[i],dp[i-1][j][k]+a[j][m-(i-k)+1]*bas[i]);
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ll max_num=0;
		for(int j=0;j<=m;j++)
			max_num=max(max_num,dp[m][i][j]);
		ans+=max_num;
	}
	cout<<ans<<endl;
	return 0; 
}

ps：经过作者后续习惯性翻翻题解（发现原来区间DP也可以做），以及打输出时的共同启发，发现实际上我们只需要分别枚举对于每一行是的最优解，加起来就可以了。因此状态中表示行的那一维可以省略。然后就有了以下代码。

点击查看代码

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int n,m;
ll a[85][85],dp[85][85];
int bas[31];
int main(){
	scanf("%d%d",&n,&m);
	bas[0]=1;
	for(int i=1;i<=30;i++) bas[i]=bas[i-1]*2;

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);

	ll ans=0,max_num;	
	for(int j=1;j<=n;j++){
		
		for(int i=1;i<=m;i++){
			dp[i][i]=dp[i-1][i-1]+a[j][i]*bas[i],dp[i][0]=dp[i-1][0]+a[j][m-i+1]*bas[i];
			for(int k=1;k<i;k++){
				dp[i][k]=max(dp[i-1][k-1]+a[j][k]*bas[i],dp[i-1][k]+a[j][m-(i-k)+1]*bas[i]);
			}
		}
		max_num=0;
		for(int i=0;i<=m;i++) max_num=max(max_num,dp[m][i]);
		ans+=max_num;
	}
	
	cout<<ans<<endl;
	return 0; 
}

事实上没太大区别，毕竟它的数据范围可以让我任性开（首尾呼应.jpg(确信)）。

summary

对于省略维数有了更深刻的理解。

可以用其他维度表示的可以省略。
可以通过分开解决时不需要整体来定义。

(dp)百道第六题。（照这个进度可能得一年后在看看有没有百道的希望了QWQ）

加油。

hmoban主题是根据ripro二开的主题，极致后台体验，无插件，集成会员系统
自学咖网 » P1005 [NOIP2007 提高组] 矩阵取数游戏

wen 普通

分享到：

前言