差亿点AK，只怪没学过状态压缩动态规划，呀嘞呀嘞dazei
学到状压DP的一个操作
枚举一个图的子图：
for(int i=n;i;i=(i-1)&n)
{
//i就是n的子图
}
n的子图关于n的补图
n； //原图
m； //n的子图
m^n； //m关于n的补图
AtCoder Beginner Contest 187 F - Close Group
题意：给一个n(n<=18)节点m条边的图，删除几个边后，使它变成几个连通子图，求最少能够变成几个子图，并且全是完全图
题解：首先枚举所有子图，如果是完全图，标记dp[i]=1，然后从小到大枚举，对一个非完全子图，再枚举其子图更新答案，由于是从小到大枚举，因此当前子图的子图肯定已经更新完了，所以可放心dp
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
#define pb push_back
inline int read(){int x;scanf("%d",&x);return x;}
int eg[20][20],dp[1<<N];
void solve()
{
int n=read(),m=read();
f(i,1,m){
int x=read(),y=read();
eg[x][y]=eg[y][x]=1;
}
int sum=(1<<n)-1;
dp[0]=999999;
for(int i=1;i<=sum;++i) //找出所有完全子图
{
vector<int>edge;
for(int j=0;j<n;j++) if(i&(1<<j)) edge.pb(j+1);
int flag=1;
for(int j=0;flag&&j<edge.size();++j)
for(int k=j+1;flag&&k<edge.size();++k)
if(!eg[edge[j]][edge[k]]) flag=0;
if(flag) dp[i]=1;
else dp[i]=999999;
}
for(int i=1;i<=sum;++i)
{
if(dp[i]==1) continue;
for(int j=i;j;j=(j-1)&i) //枚举子图，用dp[j]+dp[j^i]更新答案
{
dp[i]=min(dp[i],dp[j]+dp[j^i]);
}
}
cout<<dp[sum]<<endl;
}
int main()
{
int T=1;
while(T--) solve();
return 0;
}
再补几题状压DP
1：P1433恰奶酪
题意：给二维坐标上的n（n<=18）个点，从（0,0）出发经过所有点的最小距离
题解：dp[i][j]代表状态压缩为i的时候最后一个奶酪吃的是第j个奶酪的最小移动距离，对于一个状态，枚举最后一个点，枚举到的每个点再枚举上一个点来更新当前状态
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
#define N 18
#define INF 999999999
#define pb push_back
inline int read(){int x;scanf("%d",&x);return x;}
double dp[1<<N][N],x[N],y[N];
int BitCount(int n)//求n二进制下1的个数
{
int c =0 ;
for (c =0; n; ++c)
{
n &= (n -1) ;
}
return c ;
}
double dis(int a,int b)//距离
{
return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
void solve()
{
int n=read();
f(i,0,n-1)
cin>>x[i]>>y[i];
int sum=(1<<n)-1;
for(int i=1;i<=sum;++i)
{
f(j,0,n-1) dp[i][j]=INF;
if(BitCount(i)==1) { //如果状态只有一个点那就是到（0,0）的距离
for(int j=0;j<n;++j) if((1<<j)&i) {
dp[i][j]=dis(n,j);
break;
}
continue;
}
for(int j=0;j<n;++j) //枚举最后一个点
{
if(!((1<<j)&i)) continue;
for(int k=0;k<n;++k)//枚举连接最后一个点的上一个点来更新答案
{
if(!((1<<k)&i)) continue;
if(j==k) continue;
dp[i][j]=min(dp[i][j],dp[i&(~(1<<j))][k]+dis(k,j));
}
}
}
double ans=99999999;
f(i,0,n-1) ans=min(ans,dp[sum][i]);
printf("%.2lf",ans);
}
int main()
{
int T=1;
while(T--) solve();
return 0;
}