状态压缩dp
状压dp
Simple String Problem fzu-2218
Recently, you have found your interest in string theory. Here is an interesting question about strings.
You are given a string S of length n consisting of the first k lowercase letters.
You are required to find two non-empty substrings (note that substrings must be consecutive) of S, such that the two substrings don’t share any same letter. Here comes the question, what is the maximum product of the two substring lengths?
Input
The first line contains an integer T, meaning the number of the cases. 1 <= T <= 50.
For each test case, the first line consists of two integers n and k. (1 <= n <= 2000, 1 <= k <= 16).
The second line is a string of length n, consisting only the first k lowercase letters in the alphabet. For example, when k = 3, it consists of a, b, and c.
Output
For each test case, output the answer of the question.
Sample Input
4
25 5
abcdeabcdeabcdeabcdeabcde
25 5
aaaaabbbbbcccccdddddeeeee
25 5
adcbadcbedbadedcbacbcadbc
3 2
aaa
Sample Output
6
150
21
0
题目：选择两个子区间，这两个子区间没有相同的字母，使它们长度乘起来最大
思路：针对每一个有一些字母的状态（例：0101，B,D肯定没有，A,C，可以有可以没有），记一下它可能的最大值，最后每一项乘上它的补项就ok.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int d[1<<16];
int main(){
int t,n,k;
char str[2222];
scanf("%d",&t);
while(t--){
scanf("%d%d%s",&n,&k,str);
memset(d,0,sizeof(d));
for(int i=0; i<n; ++i){
int s=0;
for(int j=i; j<n; ++j){
s|=1<<str[j]-'a';
d[s]=max(d[s],j-i+1);
}
}
for(int i=0; i<(1<<k); ++i){
for(int j=0; j<k ;++j){
if((i>>j)&1) d[i]=max(d[i],d[(1<<j)^i]);
}
}
int res=0;
for(int i=0; i<(1<<k); ++i){
res=max(res,d[i]*d[(~i)&((1<<k)-1)]);
}
printf("%d\n",res);
}
return 0;
}
A sample Hamilton path HDU - 3538
Give you a Graph,you have to start at the city with ID zero.
Input
The first line is n(1<=n<=21) m(0<=m<=3)
The next n line show you the graph, each line has n integers.
The jth integers means the length to city j.if the number is -1 means there is no way. If i==j the number must be -1.You can assume that the length will not larger than 10000
Next m lines,each line has two integers a,b (0<=a,b<n) means the path must visit city a first.
The input end with EOF.
Output
For each test case,output the shorest length of the hamilton path.
If you could not find a path, output -1
Sample Input
3 0
-1 2 4
-1 -1 2
1 3 -1
4 3
-1 2 -1 1
2 -1 2 1
4 3 -1 1
3 2 3 -1
1 3
0 1
2 3
Sample Output
4
5
题目：求最短哈密顿路径，且有一些点必须在另外一些点的前面
思路：对于求最短哈密顿路径问题，算法竞赛进阶指南这本书上说的很好，这里主要说下后面的限制，对于1个点在一些点的前面可以用i表示这个点，F[i]表示在哪些点前面，里面也状压记一下，最后跑的时候判断一下两个节点的关系就可以了
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
int f[22];
int g[30][30];
int main(void){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
memset(f,0,sizeof(f));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&g[i][j]);
}
}
int dp[1<<n][n];
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
f[y]+=(1<<x);
}
dp[1][0]=0;
int pm=(1<<n)-1;
for(int i=1;i<=pm;i++){
for(int j=0;j<n;j++){
if(((i>>j)&1))
for(int k=0;k<n;k++){
if((g[k][j]!=-1)&&(((i^(1<<j))>>k)&1)&&(f[j]==((i^(1<<j))&f[j])))
dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+g[k][j]);
}
}
}
int minn=0x3f3f3f3f;
for(int i=0;i<n;i++)
minn=min(minn,dp[(1<<n)-1][i]);
if(minn==0x3f3f3f3f) printf("-1\n");
else printf("%d\n",minn);
}
return 0;
}
God of War HDU - 2809
At 184~280 A.D ,there were many kingdoms in China. Three strongest among them are “Wei”, “Shu”, “Wu”. People call this period as “Three Kingdoms”.
HH is a super “Three Kingdoms” fan, because at this period there were many heroes and exciting stories. Among the heroes HH worships LvBu most.
LvBu is the God of War and is also intelligent, but his ambition is too big while enemies are too powerful .Many monarchs wanted to kill him.
At 198 A.D ,CaoCao fought with LvBu at Xuzhou.Though Lvbu is the God of War ,CaoCao had so many generals: Xuchu,DianWei XiahouChun……Facing so many heroes ,could LvBu beat all of them?
Given the LvBu’s ATI, DEF, HP, and enemies’ ATI, DEF,HP, experience (if LvBu killed one of his enemies, he can get that experience ,and if his experience got more than or equal to 100*level,he would level-up and become stronger) and the In_ATI,In_DEF,In_HP(indicating when LvBu levels up,his ability will increase this point).
Each turn LvBu will choose an enemy to fight. Please help LvBu find a way to beat all of enemies and survive with the max HP.
Here’s a fight between LvBu and A:
If LvBu attack A, A will lose Max(1,LvBu’s ATI- A’s DEF) hp;
If A survived, he will give LvBu Max(1,A’ATI- LvBu’DEF) injury.
If LvBu is still alive, repeat it untill someone is dead(hp <= 0).
LvBu’s initial level is 1 and experience is 0,and he can level up many times.
Input
The input contains at most 20 test cases.
For each case , the first line contains six intergers ,indicating LvBu’s ATI,DEF,HP and In_ATI,In_DEF,In_HP.
The next line gives an interger N(0<N<=20),indicating the number of the enemies .
Then N lines followed, every line contains the name(the length of each name is no more than 20),ATI,DEF,HP, experience(1<experience<=100).
Output
If LvBu is dead output “Poor LvBu,his period was gone.”
Or output the maximum HP left.
Sample Input
100 80 100 5 5 5
2
ZhangFei 95 75 100 100
XuChu 90 90 100 90
100 75 100 5 5 5
1
GuanYu 95 85 100 100
Sample Output
30
Poor LvBu,his period was gone.
题意：和上一个题类似，状压记一下，打完了谁没打完谁，也不用从一个接点转移到令一个接点了，少了一层循环，血量经验什么的跟着dp跑跑就可以记下来（也可以每次用到现算，但我比较容易乱）
#include<iostream>
#include<algorithm>
using namespace std;
struct hero{
int att,def,hp,lev;
int exp;
}dp[(1<<20)+1];
struct enemy{
int att,def,hp,exp;
}e[25];
int att,def,hp;
void init(){
for(int i=1;i<(1<<20)+1;i++)
dp[i].hp=0;
}
int main(){
char str[25];
while(scanf("%d %d %d %d %d %d",&dp[0].att,&dp[0].def,&dp[0].hp,&att,&def,&hp)==6){
int n=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%s %d %d %d %d",str,&e[i].att,&e[i].def,&e[i].hp,&e[i].exp);
init();
dp[0].lev=1;
dp[0].exp=0;
for(int j=0;j<(1<<n)-1;j++){
if(dp[j].hp<=0)
continue;
for(int k=0;k<n;k++){
hero temp=dp[j];
if((j&(1<<k))!=0)
continue;
int sub=max(temp.att-e[k].def,1);
int sub1=max(e[k].att-temp.def,1);
int time=(e[k].hp/sub)+((e[k].hp%sub==0)?-1:0);
temp.hp-=time*sub1;
if(temp.hp<=0)
continue;
temp.exp+=e[k].exp;
if(temp.exp>=temp.lev*100){
temp.lev++;
temp.att+=att;
temp.def+=def;
temp.hp+=hp;
}
if(temp.hp>dp[j|(1<<k)].hp)
dp[j|(1<<k)]=temp;
}
}
if(dp[(1<<n)-1].hp<=0){
printf("Poor LvBu,his period was gone.\n");
continue;
}
printf("%d\n",dp[(1<<n)-1].hp);
}
return 0;
}
Tunnels HDU - 4856
Bob is travelling in Xi’an. He finds many secret tunnels beneath the city. In his eyes, the city is a grid. He can’t enter a grid with a barrier. In one minute, he can move into an adjacent grid with no barrier. Bob is full of curiosity and he wants to visit all of the secret tunnels beneath the city. To travel in a tunnel, he has to walk to the entrance of the tunnel and go out from the exit after a fabulous visit. He can choose where he starts and he will travel each of the tunnels once and only once. Now he wants to know, how long it will take him to visit all the tunnels (excluding the time when he is in the tunnels).
Input
The input contains mutiple testcases. Please process till EOF.
For each testcase, the first line contains two integers N (1 ≤ N ≤ 15), the side length of the square map and M (1 ≤ M ≤ 15), the number of tunnels.
The map of the city is given in the next N lines. Each line contains exactly N characters. Barrier is represented by “#” and empty grid is represented by “.”.
Then M lines follow. Each line consists of four integers x 1, y 1, x 2, y 2, indicating there is a tunnel with entrence in (x 1, y 1) and exit in (x 2, y 2). It’s guaranteed that (x 1, y 1) and (x 2, y 2) in the map are both empty grid.
Output
For each case, output a integer indicating the minimal time Bob will use in total to walk between tunnels.
If it is impossible for Bob to visit all the tunnels, output -1.
Sample Input
5 4
…#
…#.
…
…
…
2 3 1 4
1 2 3 5
2 3 3 1
5 4 2 1
Sample Output
7
思路：要先bfs跑一边求距离的哈密顿最短路问题
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
char map[20][20];
int dp[40000][15],n,m,dis[20][20],vis[20][20];
int dx[4]={
0,1,0,-1};
int dy[4]={
1,0,-1,0};
vector<int> mp[20][20];
bool panduan(int x,int y){
if(x<1||y<1||x>n||y>n) return false;
return true;
}
struct node{
int a,b,c,d;
}tur[20];
void bfs(int sta){
memset(vis,-1,sizeof(vis));
queue<pair<int,int> >q;
q.push(make_pair(tur[sta].c,tur[sta].d));
vis[tur[sta].c][tur[sta].d]=0;
while(!q.empty()){
int x=q.front().first, y=q.front().second;
if(mp[x][y].size())
for(int i=0;i<mp[x][y].size();i++){
dis[sta][mp[x][y][i]]=vis[x][y];}
q.pop();
for(int i=0;i<4;i++){
int newx=x+dx[i];
int newy=y+dy[i];
if(panduan(newx,newy)&&map[newx][newy]!='#'&&vis[newx][newy]==-1){
vis[newx][newy]=vis[x][y]+1;
q.push(make_pair(newx,newy));
}
}
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(dp,0x3f,sizeof(dp));
memset(dis,-1,sizeof(dis));
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
mp[i][j].clear();
for(int i=1;i<=n;i++)
scanf("%s",map[i]+1);
for(int i=0;i<m;i++){
scanf("%d%d%d%d",&tur[i].a,&tur[i].b,&tur[i].c,&tur[i].d);
mp[tur[i].a][tur[i].b].push_back(i);
}
for(int i=0;i<m;i++) bfs(i);
for(int i=0;i<m;i++) dp[1<<i][i]=0;
for(int i=1;i<1<<m;i++)
for(int j=0;j<m;j++)
if((i>>j)&1)
for(int k=0;k<m;k++)
if((dis[k][j]!=-1)&&((i>>k)&1))
dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+dis[k][j]);
int minn=0x3f3f3f3f;
for(int i=0;i<m;i++) minn=min(minn,dp[(1<<m)-1][i]);
if(minn==0x3f3f3f3f) printf("-1\n");
else printf("%d\n",minn);
}
return 0;
}
得物app公司福利 402人发布
