感觉自己 dp 非常的差，于是在这里集中整理一下。
这里都是非常初级的动态规划。
<h1>定义</h1>
何为动态规划？ 大概上就是一个不断探索问题性质减少那些和答案有关的值的个数。
动态规划重要的三部曲：
- 设计状态
- 考虑转移
- 考虑优化
由于这里是入门级别的动态规划，将不会考虑到优化。
<h1>背包问题</h1>
那我们来看一些题目吧。
<h2>BZOJ 2287</h2>
<h3>题目描述</h3>
ftiasch 有 $ N $ 个物品, 体积分别是 $W_1, W_2, \cdots , W_N $ 。 由于她的疏忽, 第 $ i $ 个物品丢失了。 要使用剩下的 $ N - 1 $ 物品装满容积为 $ x $ 的背包，有几种方法呢？-- 这是经典的问题了。她把答案记为 $ Count(i, x) $ ，想要得到所有 $ 1 \leq i \leq N, 1 \leq x \leq M $ 的 $ Count(i, x) $ 表格。
其中$ 1 \leq N \leq 2*10^3 $
$ 1 \leq M \leq 2*10^3 $
<h3>解题报告</h3>
这是一道经典的退背包问题。
我们设 $ f_i $ 表示填满容量为 $ i $ 的背包的方案数，状态转移方程显然是：
$$ f_i = f_{i-1} + f_{j-w_i}$$
然后按照题目意思，记 $ C_{i,x} $ 为不使用第 $ i $ 个物品填满容量为 $ x $ 的背包的方案数，状态转移方程显然是：
$$ C_{i,x} = \begin{cases} f_j - C_{i,x-w_j} & w_j \leq j \ f_j & w_j=j \ 1 & j=0\end{cases} $$
然后输出即可，时间复杂度 $ O(N^2) $
本质上是一个多项式除一个单项式。
<h3>参考代码</h3>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
const int MAXN = 2000 + 5;
const int ha = 10;
int a[MAXN],f[MAXN],cMAXN;
int N,M;
int main(){
scanf("%d%d",&N,&M);
for(int i = 1;i <= N;i++)
scanf("%d",a + i);
f[0] = 1;
for(int i = 1;i <= N;i++)
for(int j = M;j >= a[i];j--)
f[j] = (f[j] + f[j-a[i]])%ha;
for(int i = 1;i <= N;i++){
ci = 1;
for(int j = 1;j <= M;j++){
if(j >= a[i]) ci = (f[j] - ci] + ha) % ha;
else ci = f[j];
printf("%d",ci);
}
puts("");
}
getchar();getchar();
return 0;
}
<h2>BZOJ 4033</h2>
<h3>题目描述</h3>
有一棵点数为 $ N $ 的树，树边有边权。给你一个在 $ [0,N] $ 之内的正整数 $ K $ ，你要在这棵树中选择 $ K $ 个点，将其染成黑色，并将其他的 $ N-K $ 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。
其中 $ N \leq 2000 $ .
<h3>解题报告</h3>
我们定义状态 $ f_{v,i} $ 为以 $ v $ 为根的子树中选取 $ i $ 个黑色节点对总答案贡献的最大价值。
这里的贡献如果按照题目定义，会特别难以计算，时间复杂度飙升。
所以我们自己定义边的贡献 $ val $ 为：边一侧的黑节点数*另一侧的黑节点数*边权+一侧的白节点数*另一侧的白节点数*边权 。
那么这个就变成了一个小清新背包问题。
我们可以列出转移方程为：
$$ f_{u,i} = max(f_{u,i},f_{u,i-j}+f_{v,j} + val) $$
其中枚举 $ v $ 为 $ u $ 的子节点， $ j $ 为在以 $ v $ 为根的子树中枚举选择的黑点。 $ val $ 为该条边的贡献。
$ val=j<em>(k-j)</em>w + (v_{size}-j)<em>(N-K+j-size_v)</em>w $
其中 $ w $ 为边的边权， $ v_{size} $ 为以 $ v $ 为根的子树的节点数量。
<h3>参考代码</h3>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define LL long long
//#define max(a,b) a > b ? a : b
const int MAXN = 2000 + 5;
int N,K;
LL fMAXN;
struct Node{
struct Edge *firstEdge;
int size,num;
}node[MAXN];
struct Edge{
Node s,t;
int w;
Edge *next;
}pool[MAXN 2],frog = pool;
Edge New(Node s,Node *t,int w){
Edge *ret = ++frog;
ret->s = s;ret->t = t;
ret->w = w;ret->next = s->firstEdge;
return ret;
}
void dfs(Node v,Node fa){
v->size = 1;
fv->num = fv->num = 0;
for(Edge *e = v->firstEdge;e;e = e->next){
if(e->t == fa) continue;
dfs(e->t,v);
v->size += e->t->size;
}
for(Edge *e = v->firstEdge;e;e = e->next){
if(e->t == fa) continue;
for(int i = std::min(K,v->size);i >= 0;i--){ // 当前树选择点
for(int j = 0;j <= std::min(i,e->t->size);j++){ // 子树选择点
if(fv->num != -1){
LL val = (LL)j (K-j) e->w + (LL)(e->t->size - j) (N - K + j - e->t->size) e->w;
fv->num = std::max(fv->num,fv->num + fe->t->num + val);
}
}
}
}
}
inline void add(int u,int v,int w){
node[u].firstEdge = New(&node[u],&node[v],w);
node[v].firstEdge = New(&node[v],&node[u],w);
}
int main(){
scanf("%d%d",&N,&K);
memset(f,-1,sizeof(f));
for(int i = 1;i <= N;i++)
node[i].num = i;
for(int u,v,w,i = 1;i < N;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
dfs(&node[1],&node[0]);
printf("%lldn",f1);
getchar();getchar();
return 0;
}
<h2>总结</h2>
对于这种问题，找出题目中隐藏的容量和价值，巧妙转移问题，有时价值太难算可以自己选取一个正确好算的价值。
<h1>数位 dp</h1>
<h2>BZOJ1026</h2>
<h3>题目描述</h3>
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为 $ 2 $ 的正整数被称为windy数。 windy想知道，在 $ A $ 和 $ B $ 之间，包括 $ A $ 和 $ B $ ，总共有多少个windy数？
其中 $ 1 \leq A \leq B \leq 10^{18} $
<h3>解题报告</h3>
直接数位 dp。
设 $ f_{i,j} $ 表示考虑前 $ i $ 位，上一位是 $ i-1 $ 的方案数。
转移方程是
$$ f_{i,j} = f_{i,j} + f_{i-1,k}(j-k \geq 2) $$
直接计数统计即可。
<h3>参考代码</h3>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define LL long long
const int BASE = 12 + 5;
LL fBASE;
LL a,b;
int dight[BASE];
int len;
void init(){
memset(f,0,sizeof(f));
for(int i = 0;i <= 9;i++){
f1 = 1;
}
for(int i = 2;i <= 10;i++){
for(int j = 0;j <= 9;j++){
for(int k = 0;k <= 9;k++){
if(std::abs(j - k) >= 2)
fi += fi-1;
}
}
}
}
LL solve(LL x){
LL ret = 0;
if(!x) return 0;
memset(dight,0,sizeof(dight));
len = 0;
while(x){
dight[++len] = x % 10;
x /= 10;
}
for(int i = 1;i <= dight[len] - 1;i++)
ret += flen;
for(int i = len - 1;i > 0;i--)
for(int j = 1;j <= 9;j++)
ret += fi;
for(int i = len-1;i > 0;i--){
for(int j = 0;j <= dight[i]-1;j++)
if(std::abs(dight[i + 1]-j) >= 2) ret += fi;
if(std::abs(dight[i + 1] - dight[i]) < 2) break;
}
return ret;
}
int main(){
scanf("%lld%lld",&a,&b);
init();
printf("%lld",solve(b + 1) - solve(a));
getchar();getchar();
return 0;
}
<h2>BZOJ1799</h2>
<h3>题目描述</h3>
给出 $ a,b $ ，求出 $ [a,b] $ 中各位数字之和能整除原数的数的个数.
其中 $ 1 \leq a \leq b \leq 10^{18} $
<h3>解题报告</h3>
我们设状态 $ f[i][j][k][0/1] $ 表示考虑前 $ i $ 位，数字和为 $ j $ ，数字和 $ mod\ m $ 为 $ k $ ，是否卡上界的情况下的方案数。
转移方程在代码里，就不写了。
<h3>参考代码</h3>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define LL long long
const int BASE = 20 + 5;
const int MAX_SUM = 200 + 5;
LL fBASEMAX_SUM;
int sum = 9 * 18 + 1;
LL a,b;
int dight[BASE];
LL pre(LL x,int ha){
if(!x) return 0;
memset(f,0,sizeof(f));
int cnt = 0;
while(x){
dight[++cnt] = x % 10;
x /= 10;
}
fcnt + 10 = 1;
for(int i = cnt + 1;i > 1;i--){
for(int j = 0;j <= ha;j++){
for(int k = 0;k < ha;k++){
if(!fik && !fik) continue;
for(int p = 0;p <= 9;p++){
if(p < dight[i-1] && (j + p <= ha))
fi-1(10 * k + p)%ha += fik;
else if(p == dight[i-1] && (j + p <= ha))
fi-1(10 * k + p)%ha += fik;
if(fik && (j + p <= ha))
fi-1(10 * k + p)%ha += fik;
}
}
}
}
return f10 + f10;
}
int main(){
scanf("%lld%lld",&a,&b);
LL ans = 0;
for(int i = 1;i < sum;i++)
ans += pre(b,i) - pre(a-1,i);
printf("%lldn",ans);
getchar();getchar();
return 0;
}
<h2>总结</h2>
对于数位 dp，主要是注意位与位之间的转换的公式推导和情况特判，细心。统计答案时对上下界和其他特殊情况的特判。这种问题较为简单，有规律可循。
<h1>状压 dp</h1>
<h2>BZOJ2560</h2>
<h3>题目描述</h3>
铭铭有 $ n $ 个十分漂亮的珠子和若干根颜色不同的绳子。现在铭铭想用绳子把所有的珠子连接成一个整体。
现在已知所有珠子互不相同，用整数 $ 1 $ 到 $ n $ 编号。对于第 $ i $ 个珠子和第 $ j $ 个珠子，可以选择不用绳子连接，或者在 $ c_{i,j} $ 根不同颜色的绳子中选择一根将它们连接。如果把珠子看作点，把绳子看作边，将所有珠子连成一个整体即为所有点构成一个连通图。特别地，珠子不能和自己连接。
铭铭希望知道总共有多少种不同的方案将所有珠子连成一个整体。由于答案可能很大，因此只需输出答案对 $ 1000000007 $ 取模的结果。
其中 $ N \leq 15 $
<h3>解题报告</h3>
我们设状态 $ f_s $ 表示将状态 $ S $ 连通的方案。由于不容易直接算，我们考虑容斥原理。
设 $ g_s $ 表示所有子图的方案。
显然 $ g_s $ 可求。
对于 $ f_s $ 的计算可以由
$$ f_s = g_s - \sum_tf_t*g_{s-t} $$
计算得来。
<h3>参考代码</h3>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define ULL unsigned long long
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 20 + 5;
const int MAXS = 100000 + 5;
const int ha = 1000000007;
LL N;
LL mapMAXN,f[MAXS],g[MAXS];
void pre(LL S){
g[S] = 1;
for(LL i = 1;i <= N;i++){
if((1 << (i-1))&S)
for(LL j = i + 1;j <= N;j++)
if((1 << (j-1))&S)
g[S] = (g[S] * (mapi + 1)) % ha;
}
}
int main(int argc,char *argv[]){
scanf("%lld",&N);
for(int i = 1;i <= N;i++)
for(int j = 1;j <= N;j++)
scanf("%lld",&mapi);
for(LL i = 0;i < (1 << N);i++) pre(i);
for(LL S = 0;S < (1 << N);S++){
f[S] = g[S];
LL i = S ^ (S&-S);
for(LL j = i;j;j=(j-1)&i)
f[S] = (f[S]-g[j]*f[S^j]%ha + ha)%ha;
}
printf("%lldn",f[(1<<N)-1]%ha);
getchar();getchar();
return 0;
}
To Be Continue...
