引言
今天也复习了状态压缩 D P DP DP 和区间 D P DP DP ,这两个题型,我觉得其实不是很难,但我目前也只写过这四道模板题,不知道其他问题怎么样,不过还是心态放好吧,做的出来的就能做出来,做不出来怎么都写不对,还剩两天,加油!
一、最短Hamilton路径
标签:二进制、状态压缩DP
思路:
我们可以定义一个状态 f [ i ] [ j ] f[i][j] f[i][j] 表示其所走过的路程为 i i i ,并且最后终点为 j j j 的集合, i i i 是一个 n n n 位二进制数表示的一个十进制数,每一位的 01 01 01 状态表示该点有无走过,所以说最终的答案应该为 f [ ( 1 < < n ) − 1 ) ] [ n − 1 ] f[(1 << n) - 1)][n-1] f[(1<<n)−1)][n−1] ,我们可以从上一步推出最后一个不一样的,我们可以让其先走到 k k k 再走向 j j j ,所以说状态转移方程为 f [ i ] [ j ] = m i n ( f [ i ] [ j ] , f [ i − ( 1 < < j ) ] [ k ] + w [ k ] [ j ] ) f[i][j] = min(f[i][j],f[i-(1<<j)][k] + w[k][j]) f[i][j]=min(f[i][j],f[i−(1<<j)][k]+w[k][j]) ,搜索顺序就是一般的顺序,并且要判断 i i i 号状态是否经过 j , k j,k j,k 这两个点,详情见代码。
题目描述:
给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数 n。
接下来 n 行每行 n 个整数,其中第 i 行第 j 个整数表示点 i 到 j 的距离(记为 a[i,j])。
对于任意的 x,y,z,数据保证 a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。
输出格式
输出一个整数,表示最短 Hamilton 路径的长度。
数据范围
1≤n≤20,0≤a[i,j]≤107
输入样例:
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例:
18
示例代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 20, M = 1 << N;
int n;
int w[N][N], f[M][N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
cin >> w[i][j];
}
}
memset(f, 0x3f, sizeof f);
f[1][0] = 0;
for(int i = 1; i < 1 << n; i += 2)
{
for(int j = 0; j < n; ++j)
{
if(i >> j & 1)
{
for(int k = 0; k < n; ++k)
{
if(i >> k & 1)
{
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
}
}
}
}
}
cout << f[(1 << n) - 1][n-1] << endl;
return 0;
}
二、毕业旅行问题
标签:状态压缩DP
思路:
这道题跟上一道题基本一样,只不过起点要走两遍。其实就是走完所有的点,然后从某一个点回到起点,可以直接遍历终点然后取最小值即可 。 r e s = ∑ i = 0 n − 1 m i n ( r e s , f [ ( 1 < < n ) − 1 ] [ i ] + w [ i ] [ 0 ] ) res = \sum_{i = 0}^{n-1}min(res, f[(1 << n) - 1][i] + w[i][0]) res=i=0∑n−1min(res,f[(1<<n)−1][i]+w[i][0])
题目描述:
小明目前在做一份毕业旅行的规划。
打算从北京出发,分别去若干个城市,然后再回到北京,每个城市之间均乘坐高铁,且每个城市只去一次。
由于经费有限,小明希望能够通过合理的路线安排尽可能的省些路上的花销。
给定一组城市和每对城市之间的火车票的价钱,找到每个城市只访问一次并返回起点的最小车费花销。
注意:北京为 1 号城市。
输入格式
第一行包含一个正整数 n,表示城市个数。
接下来输入一个 n 行 n 列的矩阵,表示城市间的车票价钱。
输出格式
输出一个整数,表示最小车费花销。
数据范围
1<n≤20,包括北京车票价格均不超过 1000 元。
输入样例:
4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0
输出样例:
13
说明共 4 个城市,城市 1 和城市 1 的车费为 0,城市 1 和城市 2 之间的车费为 2,城市 1 和城市 3 之间的车费为 6,城市 1 和城
市 4 之间的车费为 5,以此类推。
假设任意两个城市之间均有单程票可买,且价格均在 1000 元以内,无需考虑极端情况。
示例代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 20, M = 1 << N;
int n;
int w[N][N], f[M][N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
cin >> w[i][j];
}
}
memset(f, 0x3f, sizeof f);
f[1][0] = 0;
for(int i = 1; i < 1 << n; i += 2)
{
for(int j = 0; j < n; ++j)
{
if(i >> j & 1)
{
for(int k = 0; k < n; ++k)
{
if(i >> k & 1)
{
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
}
}
}
}
}
int res = 2e9;
for(int i = 0; i < n; ++i) res = min(res, f[(1 << n) - 1][i] + w[i][0]);
cout << res << endl;
return 0;
}
三、石子合并
标签:动态规划、区间DP
思路:
首先状态定义 f [ l ] [ r ] f[l][r] f[l][r] 代表合并 [ l , r ] [l,r] [l,r] 所需花费的最小代价,那么状态转移可以从上一个不同来推导,由于每次肯定是两个堆合并为一个堆,我们可以从中拆分出一个分界点 k k k ,从 [ l , k ] , [ k + 1 , r ] [l,k] , [k+1,r] [l,k],[k+1,r] 中推导出 [ l , r ] [l,r] [l,r] ,所以状态转移方程为 f [ l ] [ r ] = ∑ k = l r − 1 m i n ( f [ l ] [ r ] , f [ l ] [ k ] + f [ k + 1 ] [ r ] + s [ r ] − s [ l − 1 ] ) f[l][r] = \sum_{k = l}^{r-1}min(f[l][r],f[l][k] + f[k+1][r] + s[r] - s[l-1]) f[l][r]=k=l∑r−1min(f[l][r],f[l][k]+f[k+1][r]+s[r]−s[l−1]) s s s 为前缀和数组。
题目描述:
设有 N 堆石子排成一排,其编号为 1,2,3,…,N。
每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选
择的顺序不同,合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2, 我们可以先合并 1、2 堆,代价为 4,得到 4 5 2, 又合并 1、2 堆,代价为 9,得到 9 2 ,再合
并得到 11,总代价为 4+9+11=24;
如果第二步是先合并 2、3 堆,则代价为 7,得到 4 7,最后一次合并代价为 11,总代价为 4+7+11=22。
问题是:找出一种合理的方法,使总的代价最小,输出最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数,表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数,表示最小代价。
数据范围
1≤N≤300
输入样例:
4
1 3 5 2
输出样例:
22
示例代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 310;
int n;
int w[N], s[N], f[N][N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> w[i], s[i] = w[i] + s[i-1];
for(int len = 2; len <= n; ++len)
{
for(int l = 1; l + len - 1 <= n; ++l)
{
int r = l + len - 1;
f[l][r] = 2e9;
for(int k = l; k < r; ++k) f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l-1]);
}
}
cout << f[1][n] << endl;
return 0;
}
四、游戏
标签:博弈论、DP、区间DP
思路:
首先定义状态 f [ l ] [ r ] f[l][r] f[l][r] 代表在先手状态下,从 [ l , r ] [l,r] [l,r] 能获取的最大分数,然后就是状态转移方程了,无非就是先手和后手的区别,选左边并把剩余的数加上减去选剩余数能获得的最大值,就是选左边能获得的最大值,右边同理,状态转移方程为: f [ l ] [ r ] = m a x ( w [ l ] + s [ r ] − s [ l ] − f [ l + 1 ] [ r ] , w [ r ] + s [ r − 1 ] − s [ l − 1 ] − f [ l ] [ r − 1 ] ) f[l][r] = max(w[l] + s[r] - s[l] - f[l+1][r], w[r] + s[r-1] - s[l-1] - f[l][r-1]) f[l][r]=max(w[l]+s[r]−s[l]−f[l+1][r],w[r]+s[r−1]−s[l−1]−f[l][r−1]) 然后一般这种区间 D P DP DP 都是这种顺序:长的依赖于短的,右边依赖于左边。
题目描述:
玩家一和玩家二共同玩一个小游戏。
给定一个包含 N 个正整数的序列。
由玩家一开始,双方交替行动。
每次行动可以在数列的两端之中任选一个数字将其取走,并给自己增加相应数字的分数。(双方的初始分都是 0
分)
当所有数字都被取完时,游戏结束。
分更高的一方获胜。
请计算,如果双方都采取最优策略进行游戏,则游戏结束时,双方的得分各是多少。
输入格式
第一行包含整数 N。
后面若干行包含 N 个整数,表示这个序列。注意每行不一定恰好包含一个数。
输出格式
共一行,两个整数,分别表示玩家一和玩家二的最终得分。
数据范围
2≤N≤100,数列中的数字的取值范围为 [1,200]。
输入样例:
6
4 7 2 9
5 2
输出样例:
18 11
示例代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 110;
int n;
int w[N], s[N], f[N][N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> w[i], s[i] = w[i] + s[i-1];
for(int len = 1; len <= n; ++len)
{
for(int l = 1; l + len - 1 <= n; ++l)
{
int r = l + len - 1;
f[l][r] = max(w[l] + s[r] - s[l] - f[l+1][r], w[r] + s[r-1] - s[l-1] - f[l][r-1]);
}
}
cout << f[1][n] << " " << s[n] - f[1][n] << endl;
return 0;
}