动态规划——状压、树形

问题 A: 铺砖块

时间限制: 1 Sec 内存限制: 128 MB

题目描述

现有n*m的一块地板，需要用1*2的砖块去铺满，中间不能留有空隙。问这样方案有多少种

输入

输入n，m（1<=n, m<=11)
有多组输入数据，以m=n=0结束

输出

输出铺砖块的方案数

样例输入

1 2

1 3

1 4

2 2

2 3

2 4

2 11

4 11

0 0

样例输出

144

51205

入门的状压题。0表示空着，1表示填了，把它的状态压缩成一维。

先初始化一下放横着的状态，然后暴力枚举一下转移。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 typedef long double ld;
11 typedef pair<int,int> pr;
12 const double pi=acos(-1);
13 #define rep(i,a,n) for(int i=a;i<=n;i++)
14 #define per(i,n,a) for(int i=n;i>=a;i--)
15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
16 #define clr(a) memset(a,0,sizeof(a))
17 #define pb push_back
18 #define mp make_pair
19 #define fi first
20 #define sc second
21 #define pq priority_queue
22 #define pqb priority_queue <int, vector<int>, less<int> >
23 #define pqs priority_queue <int, vector<int>, greater<int> >
24 #define vec vector
25 ld eps=1e-9;
26 ll pp=1000000007;
27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
29 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
30 ll read(){ ll ans=0; char last=' ',ch=getchar();
31 while(ch<'0' || ch>'9')last=ch,ch=getchar();
32 while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
33 if(last=='-')ans=-ans; return ans;
34 }
35 long long dp[12][3000],p[3000];
36 int main()
37 {
38     int n,m;
39     while (~scanf("%d%d",&n,&m)){
40         if (n==0 && m==0) break;
41         memset(dp,0,sizeof(dp));
42         memset(p,0,sizeof(p));
43         int k=1<<m; p[0]=1;
44         for (int i=1;i<=k;i++){
45             int t=i&(-i);
46             if (i&(t+t)) p[i]=p[i-(t+t+t)]; 
47         }
48         dp[0][k-1]=1;
49         for (int i=0;i<n;i++)
50             for (int j=0;j<k;j++)
51             if (dp[i][j]){
52                 for (int z=0;z<k;z++)
53                     if ((z&j)==z && p[z]) dp[i+1][(k-1-j)|z]+=dp[i][j];
54             }
55         printf("%lld
",dp[n][k-1]);
56     }
57     return 0;
58  }

View Code

问题 B: 导游2

时间限制: 1 Sec 内存限制: 128 MB

题目描述

宁波市的中小学生们在镇海中学参加程序设计比赛之余，热情的主办方邀请同学们参观镇海中学内的各处景点，已知镇海中学内共有n处景点。现在有n位该校的学生志愿承担导游和讲解任务。每个学生志愿者对各个景点的熟悉程度是不同的，如何将n位导游分配至n处景点，使得总的熟悉程度最大呢？要求每个景点处都有一个学生导游。

输入

有若干行：

第一行只有一个正整数n，表示有n个景点和n个学生导游。

第二行至第n+1行共n行，每行有n个以空格分隔的正整数。第i+1行的第j个数k(1≤k≤1000)，表示第i个学生导游对景点j的熟悉程度为k。

输出

只有一行，该行只有一个正整数，表示求得的熟悉程度之和的最大值。

样例输入

10 6 8

9 2 3

1 7 2

样例输出

提示

【样例说明】

第1个学生负责第3个景点，第2个学生负责第1个景点，第3个学生负责第2个景点时，熟悉程度总和为24，达到最大值。

【数据限制】

50%的数据，1≤n≤9；100%的数据，1≤n≤17。

同上，记下前面的状态，转移随意，，

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 typedef long double ld;
11 typedef pair<int,int> pr;
12 const double pi=acos(-1);
13 #define rep(i,a,n) for(int i=a;i<=n;i++)
14 #define per(i,n,a) for(int i=n;i>=a;i--)
15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
16 #define clr(a) memset(a,0,sizeof(a))
17 #define pb push_back
18 #define mp make_pair
19 #define fi first
20 #define sc second
21 #define pq priority_queue
22 #define pqb priority_queue <int, vector<int>, less<int> >
23 #define pqs priority_queue <int, vector<int>, greater<int> >
24 #define vec vector
25 ld eps=1e-9;
26 ll pp=1000000007;
27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }
31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
32 ll read(){ ll ans=0; char last=' ',ch=getchar();
33 while(ch<'0' || ch>'9')last=ch,ch=getchar();
34 while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
35 if(last=='-')ans=-ans; return ans;
36 }
37 int dp[200000],a[20][20];
38 int main()
39 {
40     int n=read();
41     for (int i=1;i<=n;i++)
42         for (int j=1;j<=n;j++) a[i][j]=read();
43     dp[0]=0; int K=1<<n;
44     for (int j=1;j<K;j++){
45         int num=0;
46         for (int k=1;k<=n;k++)
47             if (j&(1<<k-1)) num++;
48         for (int k=1;k<=n;k++) 
49             if (j&(1<<(k-1))) 
50                 dp[j]=max(dp[j],dp[j-(1<<(k-1))]+a[num][k]);    
51     } 
52     printf("%d",dp[K-1]);
53     return 0;
54  }

View Code

问题 C: 天上掉Pizza

时间限制: 3 Sec 内存限制: 128 MB

题目描述

明明喜欢Pizza，但总是缺钱。有一天，他在报纸上阅读，他最喜爱的比萨饼店��必胜客，正在对大批新Pizza运行的促销。促销的办法是：在购买一些Pizza后，可能得到一些优惠券，可以对另一些Pizza进行打折，更令人惊喜的是这些优惠券可以结合起来。但是，有一个限制，Pizza必须一个接一个买，而后得到的优惠券也不可能追溯前面已经买过的Pizza。明明想尝试若干新品Pizza，可又没有充足的钱，为了能省一些，明明费劲脑力，就请你帮他计算一下如何购买Pizza，使得其平均价格最低！平均价格是指买到Pizza的总价格/总面积，即单位面积的Pizza的价格。还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。

输入

有多组输入数据。
每组输入数据第一行为m(1<=m<=15).
接下来m行，每行前3个数pi,ai,ni(1<=pi<=10000,1<=ai<=10000,0<=nipi为编号为i的Pizza的价格，ai为编号为i的Pizza的面积，ni为购买i号Pizza能得到ni张优惠券
接下来ni*2个数，分别表示该张优惠券对xi号Pizza打折(1<=xj<=m,i<>xj)，折扣为yj(1<=yj<=50)
输入以m=0结束。

输出

输出购买m个Pizza中某一些的最低单位面积价格。保留4位小数。
(如果一个Pizza原价10，得到了一张50和一张20的优惠券，那么购买它实际所需的价值就是10*0.5*0.8=4)

样例输入

80 30 0

200 100 1 2 50

200 100 0

100 100 2 3 50 2 50

100 100 1 4 50

100 100 1 2 40

600 600 1 5 10

1000 10 1 1 50 0

样例输出

2.6667

1.5000

0.5333

提示

Pizza可以不全部购买

令dp[i]为以i为状态时用的最少的钱，而价格是固定的，我们只需要记录最小价格就好了，

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 typedef long double ld;
11 typedef pair<int,int> pr;
12 const double pi=acos(-1);
13 #define rep(i,a,n) for(int i=a;i<=n;i++)
14 #define per(i,n,a) for(int i=n;i>=a;i--)
15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
16 #define clr(a) memset(a,0,sizeof(a))
17 #define pb push_back
18 #define mp make_pair
19 #define fi first
20 #define sc second
21 #define pq priority_queue
22 #define pqb priority_queue <int, vector<int>, less<int> >
23 #define pqs priority_queue <int, vector<int>, greater<int> >
24 #define vec vector
25 ld eps=1e-9;
26 ll pp=1000000007;
27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }
31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
32 ll read(){ ll ans=0; char last=' ',ch=getchar();
33 while(ch<'0' || ch>'9')last=ch,ch=getchar();
34 while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
35 if(last=='-')ans=-ans; return ans;
36 }
37 #define N 16
38 int p[N],a[N],nu[N],t[N][N+N+5],t_[N][N+N+5];
39 double f[N],dp[1<<N];
40 int main()
41 {
42     int n,suma=0;
43     while (~scanf("%d",&n)){
44         if (n==0) break;
45         memset(p,0,sizeof(p));
46         memset(a,0,sizeof(a));
47         memset(nu,0,sizeof(nu));
48         memset(t,0,sizeof(t));
49         for (int i=1;i<(1<<N);i++) dp[i]=1e9;
50         for (int i=1;i<=n;i++){
51             p[i]=read(),a[i]=read(),nu[i]=read();
52             for (int j=1;j<=nu[i];j++) t[i][j]=read(),t_[i][j]=read();
53         }
54         int K=1<<n; dp[0]=0;
55         for (int i=0;i<K;i++){
56             for (int j=1;j<=n;j++) f[j]=1;
57             for (int j=1;j<=n;j++) 
58                 if (i&(1<<(j-1))) {
59                     for (int k=1;k<=nu[j];k++)
60                         f[t[j][k]]=f[t[j][k]]*(100-t_[j][k])/100;
61                 }           
62             for (int j=1;j<=n;j++) 
63                 if ((i&(1<<(j-1)))==0)                    
64                     dp[i+(1<<(j-1))]=min(dp[i+(1<<(j-1))],dp[i]+1.0*p[j]*f[j]);             
65         }
66         double ans=1e9;
67         for (int i=0;i<K;i++){
68             suma=0;
69             for (int j=1;j<=n;j++)
70             if (i&(1<<(j-1))) suma+=a[j];
71             ans=min(ans,dp[i]/suma);
72         }
73         printf("%.4f
",ans);   
74     }
75     return 0;
76  }

View Code

问题 D: 稀有矿井

时间限制: 1 Sec 内存限制: 128 MB

题目描述

XYZ公司已在沿太平洋东海岸位于不同地区的几个岛屿发现了5种稀有的矿藏。该公司认为，这将是一个获利最好的机会。然而，由于金融危机，该公司并没有足够的人手和金钱在所有岛屿上建立矿田。因此，公司委员会选择了一些有较高的矿石储量岛屿，并派出一名调查员对这些岛屿制作了岛上的矿石分布调查。调查结果显示，每个岛上有许多连接在一起的村庄。由于耗费时间，调查员并没有记录的地图中的所有路径。只是记下了一条到达每个村庄的路径，从一个村庄到达另一个，有一个且只有一条路径（地图绘制像一棵树）。
该公司计划在每个岛屿的其中一个村庄建立分工厂。所有在岛上不同地方挖来的5种稀有矿产将被发送到这个分工厂，后成为一个复合金属。因此途径的道路必须被重修过，才能通过数量庞大的车队。为了尽量减少对道路交通的建设成本，公司决定扩大原有的路径，而不是兴建新的道路。此外，该公司决定兴建村庄的矿田，以确保他们的工人可以进入采矿。（如果子工厂坐落在一个村庄中，矿田也可以建在该村庄。）
由于这些岛屿的矿石储量非常高，每一种罕见的矿物只需要一矿田开采即可。鉴于目前所选择的岛屿的地图，你需要找到在每个岛上的建立子工厂的最优村庄，并从该村庄开始扩展道路，以采集所有5种稀有的矿产。

输入

第一行，包含一个整数T，表示岛屿的数目。（1<=Num<=50）
每组测试数据，第一行一个整数N（5<=N<=1000）。表示岛上村庄的个数。
接下来一行，N个数，m1, m2, ... mn(0<=mi<=5),表示第i个村庄所拥有的稀有矿藏的种类，0表示该村庄没有稀有矿藏（每一个村庄至多只有一种矿藏）。
接下来N-1行，描述了这个岛上连接N个村庄的地图。
每行三个数，x，y，d(1<=x, y<=n, 1<=d<=10000), 表示从x和y两个村庄之间有一条距离为d的路。

输出

每行输出一个整数。在每个岛上所需的最少扩建道路的长度。

样例输入

1 2 3 4 5 5

1 2 100

2 3 82

3 4 73

4 5 120

4 6 108

1 1 2 3 4 5

1 2 56

1 3 100

1 4 100

2 5 100

3 6 100

样例输出

363 456

树形+状压动规，

dp[i][j]表示第i个为根状态为j的最少长度。

转移：f[x][i|j]=min(f[x][i|j],f[x][i]+f[v_][j]+c_);

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 typedef long double ld;
11 typedef pair<int,int> pr;
12 const double pi=acos(-1);
13 #define rep(i,a,n) for(int i=a;i<=n;i++)
14 #define per(i,n,a) for(int i=n;i>=a;i--)
15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
16 #define clr(a) memset(a,0,sizeof(a))
17 #define pb push_back
18 #define mp make_pair
19 #define fi first
20 #define sc second
21 #define pq priority_queue
22 #define pqb priority_queue <int, vector<int>, less<int> >
23 #define pqs priority_queue <int, vector<int>, greater<int> >
24 #define vec vector
25 ld eps=1e-9;
26 ll pp=1000000007;
27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
30 #define N 2000
31 int e,v[N],next[N],head[N],cost[N];
32 void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }
33 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
34 ll read(){ ll ans=0; char last=' ',ch=getchar();
35 while(ch<'0' || ch>'9')last=ch,ch=getchar();
36 while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
37 if(last=='-')ans=-ans; return ans;
38 }
39 int s[N],flag[N],f[N][32];
40 void dfs(int x){
41     flag[x]=0;
42     f[x][(1<<(s[x]-1))]=0;
43     int e=head[x];
44     while (e!=-1){
45         int v_=v[e],c_=cost[e];
46         if (flag[v_]){
47              dfs(v_);
48              for (int i=0;i<=31;i++)
49                 for (int j=0;j<=31;j++)
50                     f[x][i|j]=min(f[x][i|j],f[x][i]+f[v_][j]+c_);
51         }
52         e=next[e];
53     }
54 }
55 int main()
56 {
57     int T=read();
58     while (T--){
59         int n=read();
60         memset(head,255,sizeof(head)); e=0;
61         for (int i=1;i<=n;i++) s[i]=read(),flag[i]=1;
62         for (int i=1;i<=n;i++) 
63             for (int j=0;j<=31;j++) f[i][j]=1e9;
64         for (int i=1;i<=n-1;i++){
65             int a=read(),b=read(),c=read();
66             add(a,b,c);
67             add(b,a,c);
68         }
69         dfs(1);
70         int ans=1e9;
71         for (int i=1;i<=n;i++) ans=min(ans,f[i][31]);
72         printf("%d
",ans);                         
73     } 
74     return 0;
75  }

View Code

问题 E: 炮兵阵地

时间限制: 1 Sec 内存限制: 128 MB

题目描述

司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入

文件的第一行包含两个由空格分割开的正整数，分别表示N和M；

接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。

N≤100；M≤10。

输出

文件仅在第一行包含一个整数K，表示最多能摆放的炮兵部队的数量。

样例输入

5 4

PHPP

PPHH

PPPP

PHPP

PHHP

样例输出

一道很有意思的动规，

dp[i][j][k]表示第i行状态是j，第i-1行状态是k的最多炮兵部队的数量。

我们可以dfs出当前层可能状态，再记录一下前两行的状态进行转移。

最后滚动一维数组就过了。

关于这个算法的时间复杂度我给不出，，

但我们可以分析一下大概的，

由于我们枚举的是可行方案所以一维大概是60，

别问我怎么知道的，我算的实测，

那时间大概是100*60*60*60大概2000W次。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 //typedef long long ll;
10 typedef long double ld;
11 typedef pair<int,int> pr;
12 const double pi=acos(-1);
13 #define rep(i,a,n) for(int i=a;i<=n;i++)
14 #define per(i,n,a) for(int i=n;i>=a;i--)
15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
16 #define clr(a) memset(a,0,sizeof(a))
17 #define pb push_back
18 #define mp make_pair
19 #define fi first
20 #define sc second
21 #define pq priority_queue
22 #define pqb priority_queue <int, vector<int>, less<int> >
23 #define pqs priority_queue <int, vector<int>, greater<int> >
24 #define vec vector
25 ld eps=1e-9;
26 //ll pp=1000000007;
27 //ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
28 //ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
29 //void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }
31 //int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
32 int read(){ int ans=0; char last=' ',ch=getchar();
33 while(ch<'0' || ch>'9')last=ch,ch=getchar();
34 while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
35 if(last=='-')ans=-ans; return ans;
36 }
37 #define N 2000
38 int l[N],ll[N],dp[N][N],dp_[N][N],now[N],l_,ll_,n_,num[N];
39 char a[102][12];
40 void dfs(int x,int m,int t,int v,int p){
41     if(t>=m){now[++n_]=v;num[n_]=p;return;}  
42     if(a[x][t]=='P') dfs(x,m,t+3,v|(1<<t),p+1);  
43     dfs(x,m,t+1,v,p);  
44 }  
45 int main()
46 {
47     int n=read(),m=read();
48     for (int i=1;i<=n;i++) scanf("%s",a[i]);
49     l[1]=ll[1]=dp_[1][1]=0; l_=ll_=1;
50     for (int k=1;k<=n;k++){
51         memset(now,0,sizeof(now)); 
52         memset(num,0,sizeof(num)); n_=0;
53         dfs(k,m,0,0,0);
54         for(int i=1;i<=n_;++i)
55             for(int j=1;j<=l_;++j)dp[i][j]=0;
56         for (int i=1;i<=n_;i++)
57             for (int j=1;j<=l_;j++)
58                 for (int t=1;t<=ll_;t++)
59                     if (!(now[i] & l[j]) && !(now[i] & ll[t])){
60                         dp[i][j]=max(dp[i][j],dp_[j][t]+num[i]);
61                     }
62         for(int i=1;i<=n_;++i)
63             for(int j=1;j<=l_;++j) dp_[i][j]=dp[i][j];
64         for (int i=1;i<=l_;i++) ll[i]=l[i]; ll_=l_;
65         for (int i=1;i<=n_;i++) l[i]=now[i]; l_=n_;
66     }
67     int ans=0;
68     for (int i=1;i<=l_;i++)
69         for (int j=1;j<=ll_;j++) ans=max(ans,dp_[i][j]);
70     printf("%d
",ans);
71     return 0;
72  }

View Code