题目：给定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;
}
题意：有头牛，m个场地，每个牛有各自喜好的场地，把这些牛安排到场地中去，每头牛都要安放在它喜好的场地，有多少种安排方法
思路：压缩dp
// #include<bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring> // for memset
#include <vector> // push_back() // vector<int>().swap(v);
#include <set> //multiset set<int,greater<int>> //big->small
#include <map>
#include <stack> // top()
#include <queue> // front() // priority_queue<T,vector<T>,greater<T> >
#include <cmath> // auto &Name : STLName Name.
#include <utility>
#include <sstream>
#include <string> // __builtin_popcount (ans); // 获取某个数二进制位1的个数
#include <cstdlib> // rand()
#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;
}
题意：有M×N的玉米地，但其中有些是不肥沃的，不能种植。用1来代表肥沃，0代表不肥沃。另外奶牛不喜欢挨着吃，也就是说要间隔着种植，求有几种种植方式，并将计算结果对1E8取模。
思路：任然是压缩DP的入门题，但和上一题不太一样，但大致思路都是：正在处理的情况受与之相邻的情况的影响，目前看起来对压缩的理解还不是很透彻
// #include<bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring> // for memset
#include <vector> // push_back() // vector<int>().swap(v);
#include <set> //multiset set<int,greater<int>> //big->small
#include <map>
#include <stack> // top()
#include <queue> // front() // priority_queue<T,vector<T>,greater<T> >
#include <cmath> // auto &Name : STLName Name.
#include <utility>
#include <sstream>
#include <string> // __builtin_popcount (ans); // 获取某个数二进制位1的个数
#include <cstdlib> // rand()
#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\n",ans);
}
return 0;
}
题意：平面上有 n (2 ≤ n ≤ 15) 个点，现用平行于坐标轴的矩形去覆盖所有点，每个矩形至少盖两个点，矩形面积不可为0，求这些矩形的最小面积。
思路：状压DP，dp[S]表示覆盖的点集为S要用的最少矩形面积
// #include<bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring> // for memset
#include <vector> // push_back() // vector<int>().swap(v);
#include <set> //multiset set<int,greater<int>> //big->small
#include <map>
#include <stack> // top()
#include <queue> // front() // priority_queue<T,vector<T>,greater<T> >
#include <cmath> // auto &Name : STLName Name.
#include <utility>
#include <sstream>
#include <string> // __builtin_popcount (ans); // 获取某个数二进制位1的个数
#include <cstdlib> // rand()
#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;
}
题意：给出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>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring> // for memset
#include <vector> // push_back() // vector<int>().swap(v);
#include <set> //multiset set<int,greater<int>> //big->small
#include <map>
#include <stack> // top()
#include <queue> // front() // priority_queue<T,vector<T>,greater<T> >
#include <cmath> // auto &Name : STLName Name.
#include <utility>
#include <sstream>
#include <string> // __builtin_popcount (ans); // 获取某个数二进制位1的个数
#include <cstdlib> // rand()
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#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;
}
题意：N个城市间有m条单向路，分别从a到b，可以在c处交P路费，也可以直接交R路费。求从1->N 的最小花费，若不能到达，则输出‘impossible’
思路：这道题与dij 不同，若是只求能不能到达完全可以用 dij ，但是本题要求最小，每个边和点都可能通过大于1次
// #include<bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring> // for memset
#include <vector> // push_back() // vector<int>().swap(v);
#include <set> //multiset set<int,greater<int>> //big->small
#include <map>
#include <stack> // top()
#include <queue> // front() // priority_queue<T,vector<T>,greater<T> >
#include <cmath> // auto &Name : STLName Name.
#include <utility>
#include <sstream>
#include <string> // __builtin_popcount (ans); // 获取某个数二进制位1的个数
#include <cstdlib> // rand()
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#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;
}
原文：https://www.cnblogs.com/jaszzz/p/12986806.html