复杂状态的动态规划

紫皮各种……

1.最优配对问题

d(i,S) = min{|Pi,Pj| + d(i-1,S-i-j) | j在S中};

空间 n 个点，配成n/2对使两点的距离之和尽量少

for(int i = 1;i <= n;i++){
        for(int S = 0;S < (1 << n);S++){
            d[i][S] = INF;
            for(int j = 0;j < n;j++){
                if(S & (1<< j)){ /// 如果j能参与配对
                    d[i][S] = min(d[i][S],dist(i,j) + d[i-1][S^(1<<i)^(1<<j)]);
                }
            }
        }
    }

View Code

其中那个i隐含在S中所以可以转换为

int getMax(int x){
    for(int i = 31;i>=0;i--){
        int m = (x>>i)&1;
        if(m){
            return i+1;
        }
    }
    return 0;
}
for(int S = 0;S < (1<<n);S++){
        int i = getMax(S);
        d[S] = INF;
        for(int j = 0;j < n;j++){
            d[S] = min(d[S],dist(i,j) + d[i-1][s^(1<<i)^(1<<j)]);
        }
    }

View Code

2.货郎担问题

设起点城市和终点城市为0用d(i , S)表示从当前城市i 到 S的集合中城市各一次回到城里0的长度

则 d(i,S) = min{d(j,S-j) + dist(i,j) | j在S中};

3.图的色数问题

一个无相图，相邻的的颜色不能相同，求最小的颜色数

d(S) 表示把结点集S染色，所需要颜色数的最小值，则d(S) = d(S-'S') + 1;'S'为S的子集且不存在'S'内两个结点u,v两个相邻，'S'表示可以染成同一颜色的点集

通过预处理判断是够可以染成同一个颜色即内部没有边

for(int S = 1;S < (1<<n);S++){
        d[S] = INF;
        for(int S0 = S; S0;S0 = (S0-1)&S){
            if(no_edges[S0]){
                d[S] = min(d[S],d[S-S0]+1);
            }
        }
    }

View Code

uva 10817 校长的烦恼（代码没提交，233333）

m个教师n个求职者，需讲授s个课程，已知每人工资，求支付最小工资使每门课至少有两名教师能教

集合s1表示恰好只有一个人能教的课程，s2多数人教，s0每人教，d(i,s1,s2)表示要前i该状态的最小花费则转移方程为d(i,s1,s2) = min{d(i+1,s1',s2')+c[i],d(i,s1,s2)} 第i个选择聘请或不聘请，前m个是教师，不能解雇，所以前m项只能选择后者

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>

const int MAXN = 120 + 10;
const int INF = 0xffffff;
const int mod = 1000007;
const double Pi = atan(1.0)*4;
const double ESP = 10e-8;

using namespace std;

int m,n,s,c[MAXN],st[MAXN],d[MAXN][1<<10][1<<10];

int dp(int i,int s0,int s1,int s2){ ///s0表示谁都没有教，s1表示恰好有一个人能教的科目集合，s2表示可以多人教的科目集合
    if(i == m+n) ///表示最后决策，如果如果s2能够教的科目如果都能教则选择，否则不选
        return s2 == (1<<s)-1?0:INF;
    int & ans = d[i][s1][s2];
    if(ans >= 0){ ///记忆化搜索
        return ans;
    }
    ans = INF;
    if(i >= m){ ///前i个决策只能选老师，不存在不选择的情况
        ans = dp(i+1,s0,s1,s2); //不选
    }
    int m0 = st[i]&s0;  ///st[i]与s0的交集
    int m1 = st[i] & s1; ///交集
    s0 ^= m0; ///把第i个老师能教的课程从s0剔除
    s1 = (s1^m1)|m0; ///把第i个老师能教的科目从s1中剔除之后取出在s0中还有的交集
    s2 |= m1;///s2增加了能教的科目
    ans = min(ans,c[i]+dp(i+1,s0,s1,s2)); //选
    return ans;
}

int main(){
    //freopen("input.txt","r",stdin);
    while(~scanf("%d%d%d",&s,&m,&n)){
        if(!s){
            break;
        }
        memset(st,0,sizeof(st));
        memset(d,0,sizeof(d));
        for(int i = 0;i < m+n;i++){
            scanf("%d",&c[i]);
            char ch;
            int x;
            ch = getchar();
            while(ch != 10){
                scanf("%d",&x);
                ch = getchar();
                x--;
                st[i] += (1<<x);
            }
        }
        printf("%d
",dp(0,(1<<s)-1,0,0));
    }
    return 0;
}

View Code

poj 3809

n（n <=128）个物体，m个特征（m <= 11），求最小询问次数把n个物体区分开

d(s,a) 表示询问过了特征集合s，确认w具有特征a的询问次数

则下一次为 max{d(s+{k},a+{k}),d(s+{k},a)} + 1

考虑所有的k取最小值……

如果能区分的话就返回……

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#include <map>
#include <set>

using namespace std;

const int INF = 0x7ffffff;
const double ESP = 10e-8;
const double Pi = 4 * atan(1.0);
const int MAXN =   11 + 10;
const long long MOD =  1000000007;
const int dr[] = {1,0,-1,0,-1,1,-1,1};
const int dc[] = {0,1,0,-1,1,-1,-1,1};
typedef long long LL;
int d[1<<12][1<<12];
int p[1<<12];
int n,m;
int dfs(int s,int a){
    if(d[s][a] != INF){ ///如果访问过了
        return d[s][a];
    }
    int cnt = 0;
    for(int i = 0;i < n;i++){ ///统计当前特征，如果被询问过的特征中p可以被确定的个数
        if((p[i]&s) == a){
            cnt++;
        }
    }
    if(cnt <= 1){ ///如果只剩下一个或没有则就不需要进行继续询问则返回0
        d[s][a] = 0;
        return d[s][a];
    }
    for(int i = 0;i < m;i++){ ///如果被确定的个数超过了1个则需要继续询问
        if(s & (1 << i)){ ///如果第i个特征被询问过了就不需要询问
            continue;
        }
        int nn = s|(1<<i); ///询问第i个特征
        int & dd = d[s][a];
        dd = min(dd,max(dfs(nn,a),dfs(nn,a^(1<<i)))+1); ///询问i，和不询问i的最小值
    }
    return d[s][a];
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("inpt.txt","r",stdin);
   // freopen("output.txt","w",stdout);
#endif
    while(~scanf("%d%d",&m,&n)){
        if(!m && !n){
            break;
        }
        memset(p,0,sizeof(p));
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                int tmp;
                scanf("%1d",&tmp);
                if(tmp)
                    p[i] |= 1<<j;
            }
        }
        for(int i = 0;i < (1<<11)+10;i++){
            for(int j = 0;j <(1<<11)+10;j++){
                d[i][j] = INF;
            }
        }
        printf("%d
",dfs(0,0));
    }
    return 0;
}

View Code

嗨嗨嗨……数位dp总算会一点了……

开始数论初步了……

自己还是太差……