状态压缩DP
最短Hamilton路径
给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 20, M = 1 << N;
int n;
int w[N][N]; // 存每两个点之间的距离
int f[M][N]; // 上述 f[state][j]
int main(){
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &w[i][j]);
memset(f, 0x3f, sizeof f);//因为要求最小值，所以初始化为无穷大
f[1][0] = 0;
for(int i = 0; i < 1 << n; i++)
for(int j = 0; j < n; j++)
if(i >> j & 1)
for(int k = 0; k < n; k++)
if((i - (1 << j)) >> 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
没有上司的舞会
Ural 大学有 N 名职员，编号为 1∼N。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 6010;
int n;
int happy[N]; //每个职工的高兴度
int f[N][2];
int e[N],ne[N],idx,h[N];
bool has_father[N];
void add(int a,int b){
e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}
void dfs(int u){
f[u][1] = happy[u];
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
dfs(j);
f[u][0]+=max(f[j][0],f[j][1]);
f[u][1]+=f[j][0];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&happy[i]);
memset(h, -1, sizeof h);
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
has_father[a] = true;
add(b,a);
}
int root = 1;
while(has_father[root]){
root++;
}
dfs(root);
printf("%d\n",max(f[root][0], f[root][1]));
return 0;
}
记忆化搜索
滑雪
给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
在给定矩阵中，一条可行的滑行轨迹为 24−17−2−1。
在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−1，沿途共经过 25 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int n,m;
int h[N][N];//网格滑雪场
int f[N][N];//状态转移式
int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
int dp(int x,int y){
int &v = f[x][y]; //小技巧，等于把f[x][y]简化成了v，如果v发生变化，f[x][y]也会随之变化
if(v != -1) return v; //如果已经计算过了，就可以直接返回答案
v = 1;
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b]<h[x][y])
v=max(v,dp(a,b)+1);
}
return v;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&h[i][j]);
memset(f,-1,sizeof f);
int res = 0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
res=max(res,dp(i,j));
printf("%d\n",res);
return 0;
}
数位统计DP
计数问题
给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。
例如，a=1024，b=1032，则 a 和 b 之间共有 9 个数如下：
1024 1025 1026 1027 1028 1029 1030 1031 1032
其中 0 出现 10 次，1 出现 10 次，2 出现 7 次，3 出现 3 次等等…
#include<iostream>
#include<cmath>
using namespace std;
int dgt(int n)
{
int res = 0;
while(n) res++,n/=10;
return res;
}
int cnt(int n, int i) // 计算从1到n的整数中数字i出现多少次
{
int res=0,d=dgt(n);
for(int j=1;j<=d;j++){
// l和r是第j位左边和右边的整数 (视频中的abc和efg); dj是第j位的数字
int p = pow(10,j-1),l=n/p/10,r=n%p,dj=n/p%10;
// 计算第j位左边的整数小于l (视频中xxx = 000 ~ abc - 1)的情况
if(i) res += l * p;
// 如果i = 0, 左边高位不能全为0(视频中xxx = 001 ~ abc - 1)
if(!i && l) res += (l - 1) * p;
// 计算第j位左边的整数等于l (视频中xxx = abc)的情况
if ( (dj > i) && (i || l) ) res += p;
if ( (dj == i) && (i || l) ) res += r + 1;
}
return res;
}
int main(){
int a,b;
while(cin >> a >> b, a){
if(a > b) swap(a,b);
for(int i=0;i<=9;i++){
cout << cnt(b, i) - cnt(a - 1, i) << ' ';
}
cout << endl;
}
return 0;
}
