1.铺砖问题
题目：给定n*m的格子，每个格子被染成了黑色或者白色。现在要用1 * 2 的砖块覆盖这些格子，要求块与块之间互相不重叠，且覆盖了所有白色的格子，但不覆盖任意一个黑色格子。求一个有多少种覆盖方法，输出方案数对M取余后的结果。
#include<bits/stdc++.h> using namespace std; bool M[17][17]; int dp[2][1<<15]; int main(){ int n,m,mod; while(cin>>n>>m &&n&&m){ cin>>mod; memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ //从0开始后面会好操作一点 char input; cin>>input; if(input=='.') M[i][j]=0; //0:白 1：黑，将0全变为1 else M[i][j]=1; } } int *now=dp[0],*nex=dp[1]; now[0]=1; for(int i=n-1;i>=0;i--){ //从n-1 开始会方便二进制表示状态 for(int j=m-1;j>=0;j--){ for(int used=0;used< (1<<m) ;used++){ //遍历状态,这里反过来表示 if(used>>j & 1 || M[i][j]){ //假如这个位置被用了或者是1 不用填 nex[used]=now[used & ~(1<<j)]; } else{ int res=0; if(j+1<m && !(used>>(j+1)&1) && !M[i][j+1]){ //横着放 res+=now[used|1<<(j+1)]; } if(i+1<n && !M[i+1][j] ){ //竖着放 res+=now[used|1<<j]; } nex[used]=res%mod; } } swap(now,nex); } } cout<<now[0]<<endl; } return 0; }
POJ 2441 Arrange the Bulls
题意：有头牛，m个场地，每个牛有各自喜好的场地，把这些牛安排到场地中去，每头牛都要安放在它喜好的场地，有多少种安排方法
思路：压缩dp
#include<bits/stdc++.h> #define IOS ios_base::sync_with_stdio(0); cin.tie(0) #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const double PI=acos(-1.0); const int INF = 0x3f3f3f3f; const int MAX_N = 21; const int MOD = 1000000007; int dp[1<<MAX_N]; bool chose[MAX_N][MAX_N]; int main(void) { int N,M; cin>>N>>M; memset(dp,0,sizeof(dp)); for(int i=1;i<=N;i++) { int P; cin>>P; for(int j=1;j<=P;j++) { int b; cin>>b; chose[i][b]=true; } } dp[0]=1; for(int i=1;i<=N;i++) for(int s=((1<<(M+1))-1);s>=0;s--) { if(dp[s]){ for(int j=1;j<=M;j++) if(chose[i][j]&&!(s&(1<<j))) dp[s|(1<<j)]+=dp[s]; } dp[s]=0; } int ans=0; for(int s=0;s<(1<<(M+1));s++) ans+=dp[s]; cout<<ans<<endl; return 0; }
POJ 3254 Corn Fields
题意：有M×N的玉米地，但其中有些是不肥沃的，不能种植。用1来代表肥沃，0代表不肥沃。另外奶牛不喜欢挨着吃，也就是说要间隔着种植，求有几种种植方式，并将计算结果对1E8取模。
思路：任然是压缩DP的入门题，但和上一题不太一样，但大致思路都是：正在处理的情况受与之相邻的情况的影响，目前看起来对压缩的理解还不是很透彻
#include<bits/stdc++.h> #define IOS ios_base::sync_with_stdio(0); cin.tie(0) #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; int N,M,top=0; int state[600],num[110]; int dp[20][600]; int cur[20]; const int mod = 100000000; void init() { top=1; int line=1<<N; for(int i=0;i<line;i++) if((i&(i<<1))==0) state[top++]=i; top--; return; } int main(void) { while(scanf("%d%d",&M,&N)!=EOF) { init(); memset(cur,0,sizeof(cur)); memset(dp,0,sizeof(dp)); for(int i=1;i<=M;i++) { int tem; for(int j=1;j<=N;j++) { scanf("%d",&tem); if(tem==0) cur[i]+=(1<<(N-j)); } } for(int i=1;i<=top;i++) if(!(state[i]&cur[1])) dp[1][i]=1; for(int i=2;i<=M;++i) for(int k=1;k<=top;++k) if((state[k]&cur[i])==0) for(int j=1;j<=top;++j) if(((state[j]&cur[i-1])==0)&&((state[j]&state[k])==0)) dp[i][k]=(dp[i][k]+dp[i-1][j])%mod; int ans=0; for(int i=1;i<=top;i++) ans=(ans+dp[M][i])%mod; printf("%d ",ans); } return 0; }
POJ 2836 Rectangular Covering
题意：平面上有 n (2 ≤ n ≤ 15) 个点，现用平行于坐标轴的矩形去覆盖所有点，每个矩形至少盖两个点，矩形面积不可为0，求这些矩形的最小面积。
思路：状压DP，dp[S]表示覆盖的点集为S要用的最少矩形面积
#include<bits/stdc++.h> #define IOS ios_base::sync_with_stdio(0); cin.tie(0) #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; struct node { int x,y; }p[16]; int state[200],dp[1<<16],area[200]; int main(void) { int n; while(cin>>n&&n) { for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y; // 枚举n*(n-1)/2个矩形，每个矩形的有自己的状态(覆盖的点)和面积 int crt=0; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { state[crt]=(1<<j|1<<i); for(int k=0;k<n;k++) { if((p[i].x-p[k].x)*(p[k].x-p[j].x)>=0 && (p[i].y-p[k].y)*(p[k].y-p[j].y)>=0) //当一个点在这个矩形中时，把这个矩形的包含点的状态更新 state[crt]|=1<<k; } if(p[i].x==p[j].x)//特判 area[crt]=abs(p[i].y-p[j].y); else if(p[i].y==p[j].y) area[crt]=abs(p[i].x-p[j].x); else area[crt]=abs(p[i].y-p[j].y)*abs(p[i].x-p[j].x); crt++; } } memset(dp,INF,sizeof(dp)); dp[0]=0; for(int i=0;i<(1<<n);i++) for(int j=0;j<crt;j++) // i|state[j] 为第 j 个点加入到枚举情况中的情况 dp[i|state[j]]=min(dp[i|state[j]],dp[i]+area[j]); cout<<dp[(1<<n)-1]<<endl; } return 0; }
POJ 1795 DNA Laboratory
题意：给出N个字符串，求一个最小长度的串，该串包含给出的所有字符串。注意该字符串在长度最小的同时还必须是字典序最小。
这是一道涉及字符串处理的题，首先有很多字符串处理的函数要了解一下
问题：有两个字符串a、b, 现想判断a字符串是否包含b字符串。
>> 先说说string::npos参数：
npos 是一个常数，用来表示不存在的位置，类型一般是std::container_type::size_type 许多容器都提供这个东西。
>> 再来说说find函数：
find函数的返回值是整数，假如字符串存在包含关系，其返回值必定不等于npos，但如果字符串不存在包含关系，
那么返回值就一定是npos。所以不难想到用if判断语句来实现！
# include <iostream> # include <string> using namespace std; int main() { int number; cin >> number; while (number--) { string a, b; cin >> a >> b; int pos = a.find(b); if (pos == string::npos) { cout << "NO" << endl; } else { cout << "YES" << endl; } } }
substr函数的用法： 0. 用途：一种构造string的方法 1. 形式：s.substr(pos, n) 2. 解释：返回一个string，包含s中从pos开始的n个字符的拷贝（pos的默认值是0，n的默认值是s.size() - pos，即不加参数会默认拷贝整个s） 3. 补充：若pos的值超过了string的大小，则substr函数会抛出一个out_of_range异常；
若pos+n的值超过了string的大小，则substr会调整n的值，只拷贝到string的末尾
#include<bits/stdc++.h> #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int maxn=17; int n, dp[maxn][1 << maxn]; string str[maxn], ans; int cost[maxn][maxn]; //cost[i][j]表示将j字符串 void init() { for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i != j && str[i].find(str[j]) != string::npos) str[j] = str[i]; // 序列j包含i，只保留母串 stable_sort(str,str+n); // sort与stable_sort唯一的差别就是stable_sort是一种稳定的排序，在两个元素相同的时候不交换位置，而sort则不是 n=unique(str,str+n)-str; // 去重 memset(cost,0,sizeof(cost)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++) { if(i!=j) { int len=min(str[i].length(), str[j].length()); for(int k=0;k<len;k++) { if(str[i].substr(str[i].length() - k)==str[j].substr(0, k)) { cost[i][j]=str[i].length()-k; } } } } } return; } void dfs(int id, int s) { if(s == 0) return; string tmp; int next_id=-1; for(int i = 0; i < n; i++) if(i != id && (s >> i & 1)) { if(dp[id][s] == dp[i][s & ~(1 << id)] + cost[id][i]) { string t = str[i].substr(str[id].length()-cost[id][i], str[i].length()); if(next_id == -1 || t < tmp) { tmp = t; next_id = i; } } } ans += tmp; dfs(next_id, s & ~(1 << id)); } int main(void) { int T,kase=0; cin>>T; while(T--) { cin>>n; for(int i=0;i<n;i++) cin>>str[i]; if(n<=1) ans=str[0]; else{ init(); for(int i=0;i<=n;i++) fill(dp[i],dp[i]+(1<<n),INF); for(int i=0;i<n;i++) dp[i][1<<i]=str[i].length(); for(int s = 0; s < 1 << n; s++) { for(int j = 0; j < n; j++) if(dp[j][s] != INF && (s >> j & 1)) { for(int i = 0; i < n; i++) if(!(s >> i & 1)) { dp[i][s|1<<i] = min(dp[i][s|1<<i],dp[j][s]+cost[i][j]); } } } int id=0; for(int i=1;i<n;i++) if(dp[i][(1<<n)-1]<dp[id][(1<<n)-1]) id = i; ans=str[id]; dfs(id,(1<<n)-1); } cout<<"Scenario #"<<++kase<<":"<<endl; cout<<ans<<endl; cout<<endl; } return 0; }
POJ 3411 Paid Roads
题意：N个城市间有m条单向路，分别从a到b，可以在c处交P路费，也可以直接交R路费。求从1->N 的最小花费，若不能到达，则输出‘impossible’
思路：这道题与dij 不同，若是只求能不能到达完全可以用 dij ，但是本题要求最小，每个边和点都可能通过大于1次
#include<bits/stdc++.h> #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; int m,n,mcost; int vis[11]; struct node { int a,b,c,p,r; }road[11]; void DFS(int a,int fee) { if(a==n&&mcost>fee) { mcost=fee; return; } for(int i=1;i<=m;i++) { if(a==road[i].a&&vis[road[i].b]<=3) { int b=road[i].b; vis[b]++; if(vis[road[i].c]) DFS(b,fee+road[i].p); else DFS(b,fee+road[i].r); vis[b]--; } } return; } int main(void) { while(cin>>n>>m) { memset(vis,0,sizeof(vis)); vis[1]=1; mcost=INF; for(int i=1;i<=m;i++) cin>>road[i].a>>road[i].b>>road[i].c>>road[i].p>>road[i].r; DFS(1,0); if(mcost<INF) cout<<mcost<<endl; else cout<<"impossible"<<endl; } return 0; }