状压dp

Posted on 2024-05-30 In acm , dp
Symbols count in article: 955 Reading time ≈ 1 mins.

状压dp

背包问题

如果要表示物品放不放：如果五个物品都不放，可以用00000表示；如果五个物品都放，可以用11111表示

可以用一个维度表示所有物品放与不放的情况，这个过程就叫做状态压缩

#include<stdio.h>
const int INF = 1 << 15;
int dp[INF + 10];
int dp1[INF+ 10] ;	//定义状态 
void print1(int num);
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		int W[20],C[20];
		for(int i = 0; i < n; i++)
		scanf("%d %d",&C[i],&W[i]) ;
		int res = -1;
		for(int i = 0; i < (1 << n); i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(!(i&(1 << j)))		//状态转移 
				{
					int temp = i | (1<<j);
					dp[temp] = dp[i] + W[j];		
					dp1[temp] = dp1[i] + C[j];
					
				}
			}
		}
		for(int i = 0; i < (1 << n); i++)
		{
			print1(i);
			printf("\t%d\t%d\n",dp[i],dp1[i]);		//打印出每种方案的情况，价值 和耗费的空间 
		}
		
	}
	return 0;
}
void print1(int num)
{
	int k= 0;
	if(num == 0)
	printf("0");
	for(;(1 << k) <= num; k++)
	{
		if(num & (1<<k))
		printf("1");
		else
		printf("0");
	}
}

数位dp

Posted on 2024-05-30 In acm , dp
Symbols count in article: 1.9k Reading time ≈ 2 mins.

数位dp

要求统计满足一定条件的数的数量

这些条件经过转化后可以使用数位的思想去理解和判断

输入会提供一个数字区间来作为统计的限制

上界很大，暴力枚举验证会超时

sample1

求a~b中不包含49的数的个数

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int a, b, shu[20], dp[20][2];

int dfs(int len, bool if4, bool shangxian)
{
    if (len == 0)
        return 1;
    if (!shangxian && dp[len][if4])   //为什么要返回呢？可以画图理解当我们搜到3XXX时，程序运行到1XXX时就已经把3XXX之后的搜索完了，记忆化也是这个用意.
        return dp[len][if4];
    int cnt = 0, maxx = (shangxian ? shu[len] : 9);//找到每一位的上限
    for (int i = 0; i <= maxx; i++)
    {
        if (if4 && i == 9)//如果上一位是4且这一位是9则跳过
            continue;
        cnt += dfs(len - 1, i == 4, shangxian && i == maxx);  //只有之前有限制现在的达到了上限才能构成限制
    }
    return shangxian ? cnt : dp[len][if4] = cnt; //如果有限制，那么就不能记忆化，否则记忆的是个错误的数.
}

int solve(int x)
{
    memset(shu, 0, sizeof(shu));
    int k = 0;
    while (x)
    {
        shu[++k] = x % 10;  //保存a,b的数
        x /= 10;
    }
    return dfs(k, false, true);
}

int main()
{
    scanf("%d%d", &a, &b);
    printf("%d\n", solve(b) - solve(a - 1));

    //while (1);
    return 0;
}

sample2

求a~b之间有多少个不含前导0且相邻两个数字之差至少为2的正整数

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int shu[100];
ll dp[100][100];
ll dfs(ll pos,bool limit,bool zero,int last)
{
    if(pos==-1)
    return 1;
    if(!limit&&!zero&&dp[pos][last]+1)
    return dp[pos][last];
    int up;
    if(limit)
    up=shu[pos];
    else
    up=9;
    ll tem=0;
    for(int i=0;i<=up;++i)
    {
        if(abs(last-i)<2)
        continue;
        if(zero&&i==0)
        tem+=dfs(pos-1,limit&&i==up,1,-22);
        else
        tem+=dfs(pos-1,limit&&i==up,0,i);
    }
    if(!limit&&!zero)
    dp[pos][last]=tem;
    return tem;

}
ll solve(ll t)
{
    memset(dp,-1,sizeof(dp));
    int ans=0;
    while(t)
    {
        shu[ans++]=t%10;
        t/=10;
    }
    return dfs(ans-1,1,1,-2);
}
int main()
{
    ll a,b;
    cin>>a>>b;
    printf("%lld",solve(b)-solve(a-1));
}

树形dp

Posted on 2024-05-30 In acm , dp
Symbols count in article: 226 Reading time ≈ 1 mins.

树形dp

树的遍历，用DFS从根节点开始进行记忆化搜索
从树最深处开始往回进行DP，用子节点dp值来更新父节点dp值

板子

void dfs(int u)
{
	dp[u][...] = ...; 			//初始化
	for(int i=0; i < edge[u].size(); i++)	//遍历处理u的子节点v
	{
		int v = edge[u][i];
        	dfs(v);				//深搜子结点
        	dp[u][...] = ...;		//状态转移方程
   	}
}

区间dp

Posted on 2024-05-30 In acm , dp
Symbols count in article: 1.4k Reading time ≈ 1 mins.

区间dp

什么是区间dp？

区间dp就是在***区间上进行[动态规划]***，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法

核心思路

那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可

1.可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），

2.内层枚举该长度下可以的起点。

3.然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解

4.写出特定的状态转移方程(重点)

板子

for(int len = 1;len<=n;len++){//枚举长度
        for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
            }
        }
    }

四边形不等式优化

1.区间包含的单调性：如果对于i≤i’<j≤j’，有 cost(i’,j)≤cost(i,j’)，那么说明 cost 具有区间包含的单调性。（可以形象理解为如果小区间包含于大区间中，那么小区间的cost值不超过大区间的cost值），证明可通过题目定义的cost(i,j)的含义进行论证

2、四边形不等式：如果对于i≤i’<j≤j’，有 cost(i,j)+cost(i’,j’)≤cost(i’,j)+cost(i,j’)，我们称函数 cost 满足四边形不等式。（可以形象理解为两个交错区间的cost的和不超过小区间与大区间的cost的和——(交叉小于包含)）
两个定理：
1、如果上述的cost 函数同时满足区间包含单调性和四边形不等式性质，那么函数 dp也满足四边形不等式性质我们再定义s(i,j)表示dp(i,j) 取得最优值时对应的下标k（即 i≤k≤j 时，k 处的 dp 值最最优，则 s(i,j)=k）。此时有如下定理:
2、假如 dp(i,j) 满足四边形不等式，那么 s(i,j)(自变量为i、j两个变量) 单调，即s(i,j)≤s(i,j+1)≤s(i+1,j+1)

即原来的状态转移方程可以改写为下式：
dp(i,j)=min{dp(i,k-1),dp(k,j)}+cost(i,j)(s(i,j-1)≤k≤s(i+1,j))

for(int len=2;len<=n;len++) {	//枚举长度
   		for(int i=1;i<=n-len+1;i++) {
   			int j=i+len-1;	//根据起点推终点
   			dp[i][j]=Integer.MAX_VALUE;	//初始化值
   			for(int k=s[i][j-1];k<=s[i+1][j];k++) {	//通过平行四边形优化，缩小枚举范围
   				if(dp[i][k]+dp[k+1][j]+cost[j]-cost[i-1]<dp[i][j]) {	//换成if语句，可以减少不必要的循环赋值
   					dp[i][j]=dp[i][k]+dp[k+1][j]+cost[j]-cost[i-1];
   					s[i][j]=k;	//记录最优分割点
   				}
   			}
   			
   		}
   	}

概率dp

Posted on 2024-05-30 In acm , dp
Symbols count in article: 2.5k Reading time ≈ 2 mins.

概率dp

dp求概率

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int w, b;
double dp[1010][1010];

int main() {
  scanf("%d %d", &w, &b);
  memset(dp, 0, sizeof(dp));
  for (int i = 1; i <= w; i++) dp[i][0] = 1;  // 初始化
  for (int i = 1; i <= b; i++) dp[0][i] = 0;
  for (int i = 1; i <= w; i++) {
    for (int j = 1; j <= b; j++) {  // 以下为题面概率转移
      dp[i][j] += (double)i / (i + j);
      if (j >= 3) {
        dp[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) /
                    (i + j - 2) * dp[i][j - 3];
      }
      if (i >= 1 && j >= 2) {
        dp[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * i /
                    (i + j - 2) * dp[i - 1][j - 2];
      }
    }
  }
  printf("%.9lf\n", dp[w][b]);
  return 0;
}

dp求期望

#include <cstdio>
using namespace std;
int n, s;
double dp[1010][1010];

int main() {
  scanf("%d %d", &n, &s);
  dp[n][s] = 0;
  for (int i = n; i >= 0; i--) {
    for (int j = s; j >= 0; j--) {
      if (i == n && s == j) continue;
      dp[i][j] = (dp[i][j + 1] * i * (s - j) + dp[i + 1][j] * (n - i) * j +
                  dp[i + 1][j + 1] * (n - i) * (s - j) + n * s) /
                 (n * s - i * j);  // 概率转移
    }
  }
  printf("%.4lf\n", dp[0][0]);
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2010;
int n, m, v, e;
int f[maxn][maxn], c[maxn], d[maxn];
double dp[maxn][maxn][2], p[maxn];

int main() {
  scanf("%d %d %d %d", &n, &m, &v, &e);
  for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
  for (int i = 1; i <= n; i++) scanf("%lf", &p[i]);
  for (int i = 1; i <= v; i++)
    for (int j = 1; j < i; j++) f[i][j] = f[j][i] = 1e9;

  int u, V, w;
  for (int i = 1; i <= e; i++) {
    scanf("%d %d %d", &u, &V, &w);
    f[u][V] = f[V][u] = min(w, f[u][V]);
  }

  for (int k = 1; k <= v; k++)
    for (int i = 1; i <= v; i++)  // 前面的，按照前面的题解进行一个状态转移
      for (int j = 1; j < i; j++)
        if (f[i][k] + f[k][j] < f[i][j]) f[i][j] = f[j][i] = f[i][k] + f[k][j];

  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++) dp[i][j][0] = dp[i][j][1] = 1e9;

  dp[1][0][0] = dp[1][1][1] = 0;
  for (int i = 2; i <= n; i++)  // 有后效性方程
    for (int j = 0; j <= min(i, m); j++) {
      dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]],
                        dp[i - 1][j][1] + f[c[i - 1]][c[i]] * (1 - p[i - 1]) +
                            f[d[i - 1]][c[i]] * p[i - 1]);
      if (j != 0) {
        dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * p[i] +
                              f[c[i - 1]][c[i]] * (1 - p[i]),
                          dp[i - 1][j - 1][1] +
                              f[c[i - 1]][c[i]] * (1 - p[i - 1]) * (1 - p[i]) +
                              f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] +
                              f[d[i - 1]][c[i]] * (1 - p[i]) * p[i - 1] +
                              f[d[i - 1]][d[i]] * p[i - 1] * p[i]);
      }
    }

  double ans = 1e9;
  for (int i = 0; i <= m; i++) ans = min(dp[n][i][0], min(dp[n][i][1], ans));
  printf("%.2lf", ans);

  return 0;
}