# 108 条题解

• @ 2018-02-24 21:04:52

TSP实现

思路：经典TSP是找出一个权值和最小环。既然这道题只要访问所有节点，不用考虑环，那么 只要把TSP起点设为拥有1个元素的集合即可

哎，状压DP做TSP的性能总是让人不满意，最后几个点都700多ms，几乎时卡着时限过了

#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 16
#define INF 2100000000
using namespace std;

int n;
int cm[MAXN][MAXN];
int dp[1 << MAXN][MAXN] = {0};

int main(){

cin >> n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> cm[i][j];
}
}
int ans = INF;
for(int stage=0; stage<n; stage++){
memset(dp, 0, sizeof dp);
int preset = 1 << stage;
for(int i=0; i< (1 << n); i++){
if(i == preset) continue;
for(int j=0; j<n; j++){
dp[i][j] = INF;
}
}
for(int i=preset+1; i< (1 << n); i++){
if((i >> stage)&1 == 0) continue;
for(int v=0; v<n; v++){
for(int u=0; u<n; u++){
if((i >> u)&1 == 0) continue;
if(u == v) continue;
dp[i][v] = min(dp[i][v], dp[i&(~(1 << u))][u]+cm[u][v]);
}
}
}
ans = min(ans, dp[(1 << n)-1][stage]);
}
cout << ans;

return 0;
}

评测情况

Accepted
/in/foo.cc: In function 'int main()':
/in/foo.cc:31:31: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
if((i >> stage)&1 == 0) continue;
~~^~~~
/in/foo.cc:34:35: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
if((i >> u)&1 == 0) continue;
~~^~~~
#   状态  耗时  内存占用
#1   Accepted   8ms 4.25 MiB
#2   Accepted   7ms 4.25 MiB
#3   Accepted   7ms 4.344 MiB
#4   Accepted   8ms 4.25 MiB
#5   Accepted   7ms 4.359 MiB
#6   Accepted   10ms    4.25 MiB
#7   Accepted   12ms    4.367 MiB
#8   Accepted   14ms    4.352 MiB
#9   Accepted   23ms    4.359 MiB
#10  Accepted   45ms    4.34 MiB
#11  Accepted   87ms    4.25 MiB
#12  Accepted   167ms   4.371 MiB
#13  Accepted   304ms   4.371 MiB
#14  Accepted   739ms   4.375 MiB
#15  Accepted   728ms   4.391 MiB
#16  Accepted   716ms   4.34 MiB
#17  Accepted   676ms   4.336 MiB
#18  Accepted   716ms   4.477 MiB
#19  Accepted   733ms   4.371 MiB
#20  Accepted   7ms 4.352 MiB

• @ 2017-10-21 13:30:36
#include <cstdio>
#include <iostream>
#include<cstring>
using namespace std;
int n,a[20][20],dp[1<<16][20],ans=0x3f3f3f3f;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<n;i++)
dp[1<<i][i+1]=0;
for(int i=1;i<1<<n;i++)
for(int j=1;j<=n;j++)
if(dp[i][j]!=0x3f3f3f3f)
for(int k=0;k<n;k++)
if(!(i&(1<<k)))
dp[i|(1<<k)][k+1]=min(dp[i|(1<<k)][k+1],dp[i][j]+a[j][k+1]);
for(int i=1;i<=n;i++)
ans=min(ans,dp[(1<<n)-1][i]);
printf("%d",ans);
}

• @ 2017-09-05 13:27:19

很水的状压dp qwq

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;

int n;
int dis[20][20];
int f[20][1<<16];

int dfs(int u, int s){
if(s==((1<<n)-1)) return 0;
if(f[u][s]!=-1) return f[u][s];
int ret=987654321;
for(int i=1;i<=n;i++)
if(!(s&1<<(i-1)))
ret=min(ret, dfs(i, s|1<<(i-1))+dis[u][i]);
return f[u][s]=ret;
}

int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d", &dis[i][j]);
memset(f, -1, sizeof(f));
cout<<dfs(0, 0)<<endl;
return 0;
}

• @ 2017-10-18 16:51:09

哎，蒟蒻写了一节课，还调了一节课，向大佬低头

• @ 2016-11-16 11:19:22
c++
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,i,j,ans=1<<30,judge,hash,a[20][20];
void dfs(int x,int now)
{
if(now>ans)return;
if(hash==judge){ans=min(ans,now);return;}
for(int j=1;j<=n;j++)
if(a[x][j]!=-1&&((hash>>(j-1))%2==0))
hash+=1<<(j-1),
dfs(j,now+a[x][j]),
hash-=1<<(j-1);
}
int main()
{
//  freopen("pass.in","r",stdin);
//    freopen("pass.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
judge+=1<<(i-1);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
hash=1<<(i-1),
dfs(i,0);
printf("%d",ans);
return 0;
}

为啥CE

• @ 2019-05-17 11:19:38
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxv = 0x3f3f3f3f;
int f[1 << 16][20], n, c[20][20], ans = maxv;

int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> c[i][j];
}
}

memset(f, 0x3f, sizeof f);

for (int i = 0; i < n; i++) f[1 << i][i + 1] = 0;

for (int s = 1; s < (1 << n); s++) {
for (int i = 1; i <= n; i++) {
if (f[s][i] != maxv) {
for (int j = 0; j < n; j++) {
if ((1 << j) & s) continue;
int ns = ((1 << j) | s);
f[ns][j + 1] = min(f[s][i] + c[i][j + 1], f[ns][j + 1]);
}
}
}
}

for (int i = 1; i <= n; i++) ans = min(ans, f[(1 << n) - 1][i]);
cout << ans << endl;
return 0;
}

• @ 2019-03-16 12:20:19

特别水
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=20;
int pass[maxn][maxn];
int dp[65536][maxn];
int n;
int minx(int a,int b){
if(a==-1) return b;
if(b==-1) return a;
return a<b?a:b;
}
int main(){
scanf("%d",&n);

for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&pass[i][j]);
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++) dp[1<<i][i]=0;
int ans=-1;
for(int i=0;i< (1<<n);i++){
for(int j=0;j<n;j++){
if(dp[i][j]!=-1){
for(int k=0;k<n;k++){
if((1<<k)&i)continue;
dp[i|(1<<k)][k]=minx(dp[i|(1<<k)][k],dp[i][j]+pass[j][k]);
if((i|(1<<k))==(1<<n)-1) ans=minx(ans,dp[i|(1<<k)][k]);
}
}
}
}
if(ans!=-1) printf("%d",ans);
else if(ans==-1) printf("0");
return 0;
}

• @ 2017-10-21 19:48:32

一开始直接就是打的搜索，过了九个点，￣へ￣
WRONG：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<string>
#define ll long long
#define inf 214748364
#define DB double
using namespace std;
{
int x=0,w=1;char ch=0;
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*w;
}
int f[20][20],n,ans;
bool v[20];
void dfs(int x,int sum,int cnt)
{
if(sum>ans) return;
if(cnt==n)
{
ans=min(ans,sum);
return;

}
//cout<<x<<" "<<sum<<" "<<cnt<<endl;
for(int i=1;i<=n;i++)
if(v[i]==0)
{
v[i]=1;
dfs(i,sum+f[x][i],cnt+1);
v[i]=0;
}
}
int main()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int i=1;i<=n;i++)
{
memset(v,0,sizeof(v));
v[i]=1;
dfs(i,0,1);
//break;
}
printf("%d",ans);
return 0;
}
但是正解是状压DP：
后来又一直WA两个点，请students debug 发现，原来是状态少了，哎，
还是状压DP的菜鸟，什么时候才能成长。
（致即将参加NOIP的自己）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<string>
#define ll long long
#define inf 1179010630
#define DB double
using namespace std;
{
int x=0,w=1;char ch=0;
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*w;

}
int v[20][20],n,ans;
int f[132000][20],to,aim;
//f[i][j]表示状态为i,当前物品在j这个人手上的最小代价
int main()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
memset(f,70,sizeof(f));
for(int i=1;i<=n;i++)aim=aim+(1<<i);//我的目标状态
for(int i=0;i<=n;i++)
f[(1<<i)][i]=0;
for(int i=1;i<=aim;i++)
for(int j=1;j<=n;j++)
if(f[i][j]!=inf)//没有这句话也可以，反正f[i][j]初始是极大值
for(int k=1;k<=n;k++)
if((i&(1<<k))==0)
{
to=(i|(1<<k));//由i转移到的状态
f[to][k]=min(f[to][k],f[i][j]+v[j][k]);
//cout<<to<<" "<<j<<" "<<k<<endl;
}
for(int i=1;i<=n;i++)
ans=min(ans,f[aim][i]);
printf("%d",ans);
return 0;

}

• @ 2017-08-19 23:35:57
//就是要提醒一下，一定要注意括号，一不小心就WA了三次，唉...
#include<iostream>
#include<cstring>
using namespace std;
int dp[70000][17],far[17][17];

int minn(int a,int b)
{
if(a==-1)
return b;
if(b==-1)
return a;
if(a<b)
return a;
else
return b;
}

int main()
{
int n,ans=-1,i,j,k;
cin>>n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>far[i][j];
memset(dp,-1,sizeof(dp));
for(i=0;i<n;i++)
{
dp[1 << i][i]=0;
}
for(i=0;i < 1 << n;i++)
{
for(j=0;j<n;j++)
{
if(dp[i][j]!=-1)
{
for(k=0;k<n;k++)
{
if(!(i&(1 << k)))
{
dp[i | (1 << k)][k]=minn(dp[i | (1 << k)][k],dp[i][j]+far[j][k]);
if((i | (1 << k))==(1 << n)-1)//一开始就是这里掉了括号QAQ
ans=minn(ans,dp[i|(1 << k)][k]);
}
}
}
}
}
cout<<ans;
return 0;
}

• @ 2017-05-05 11:47:51
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
#include<cstring>
#include<vector>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(ll i=j;i<=k;i++)
#define Dow(i,j,k) for(ll i=k;i>=j;i--)
using namespace std;
ll n,v[101][101],ans=1e9,cnt,f[100001][20];
bool vis[101];
void dfs(ll x,ll alr,ll sum,ll now)
{
if(alr==n-1)
{
ans=min(ans,sum);
return;
}
if(sum>=f[now][x])  return;
f[now][x]=sum;
For(i,1,n)
{
if(i==x||vis[i])    continue;
vis[i]=1;
dfs(i,alr+1,sum+v[i][x],now|(1<<(i-1)));
vis[i]=0;
}
}
int main()
{
scanf("%lld",&n);
For(i,1,n)
For(j,1,n)  scanf("%lld",&v[i][j]);
For(i,1,100000) For(j,1,n)f[i][j]=1e9;
For(i,1,n)  memset(vis,0,sizeof vis),vis[i]=1,dfs(i,0,0,1<<(i-1));
printf("%lld",ans);
}

记忆化暴搜

• @ 2016-05-10 22:29:06

#include <stdio.h>
include <string.h> include <iostream> include <queue>
using namespace std;
queue<int> q;
int f[65537][17];
int mc[18]={0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536};
int main (){
int n,i,j;
scanf ("%d",&n);
int k[n+1][n+1];
for (i=1;i<=n;i++)
{for (j=1;j<=n;j++)
{scanf ("%d",&k[i][j]);}
}
memset (f,0x7f,sizeof(f));
bool in[65537];
memset (in,0,sizeof(in));
for (i=1;i<=n;i++)
{f[mc[i]][i]=0;q.push(mc[i]);in[mc[i]]=1;}
while (q.size()>1)
{int d=q.front();q.pop();in[d]=0;
for (i=1;i<=n;i++)
{if ((mc[i]&d)==0)
{for (j=1;j<=n;j++)
{if ((mc[j]&d)!=0)
{if (f[mc[i]+d][i]>f[d][j]+k[j][i])
{f[mc[i]+d][i]=f[d][j]+k[j][i];
if (!in[mc[i]+d]) {q.push(mc[i]+d);in[mc[i]+d]=1;}
}
}
}
}
}
}
int minn=10000000;
for (i=1;i<=n;i++)
{if (f[mc[n+1]-1][i]<minn) {minn=f[mc[n+1]-1][i];}
}
printf ("%d\n",minn);
return 0;
}

• @ 2016-05-10 22:28:46

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int f[65537][17];
int mc[18]={0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536};
int main (){
int n,i,j;
scanf ("%d",&n);
int k[n+1][n+1];
for (i=1;i<=n;i++)
{for (j=1;j<=n;j++)
{scanf ("%d",&k[i][j]);}
}
memset (f,0x7f,sizeof(f));
bool in[65537];
memset (in,0,sizeof(in));
for (i=1;i<=n;i++)
{f[mc[i]][i]=0;q.push(mc[i]);in[mc[i]]=1;}
while (q.size()>1)
{int d=q.front();q.pop();in[d]=0;
for (i=1;i<=n;i++)
{if ((mc[i]&d)==0)
{for (j=1;j<=n;j++)
{if ((mc[j]&d)!=0)
{if (f[mc[i]+d][i]>f[d][j]+k[j][i])
{f[mc[i]+d][i]=f[d][j]+k[j][i];
if (!in[mc[i]+d]) {q.push(mc[i]+d);in[mc[i]+d]=1;}
}
}
}
}
}
}
int minn=10000000;
for (i=1;i<=n;i++)
{if (f[mc[n+1]-1][i]<minn) {minn=f[mc[n+1]-1][i];}
}
printf ("%d\n",minn);
return 0;
}

• @ 2015-08-27 15:42:16

经典的状态压缩DP
代码
//package ds;

import java.util.*;
import java.math.*;
import java.io.*;

public class Main {
static Scanner cin = null;
static PrintStream cout = null;
static final int MAXN = 20;
static int INF = 0x3f3f3f3f;
static int[][] V = new int[MAXN][MAXN];
static int[][][][] dp = new int[2][MAXN][MAXN][MAXN];

static int Bit_Count(int val) {
int ret = 0;
while (val > 0) {
val &= (val - 1);
ret++;
}
return ret;
}

public static void main(String[] agrs) throws IOException {
//System.setIn(new FileInputStream(new File("D:" + File.separator + "imput.txt")));
cin = new Scanner(System.in);
cout = new PrintStream(System.out);

while (cin.hasNext()) {
int n = cin.nextInt();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
V[i][j] = cin.nextInt();
}
}
for (int i = 0; i < 2; i++) {
for (int f = 1; f <= n; f++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (i == 1)
dp[i][f][j][k] = 0;
else
dp[i][f][j][k] = INF;
if (i == 0 && f == 0)
dp[i][f][j][k] = 0;
}
}
}
}
int Min = INF;
for (int i = 1; i < n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (j == k)
continue;
for (int f = 1; f <= n; f++) {
if (f == j)
continue;
if ((dp[1][i - 1][f][j] & (1 << k)) > 0)
continue;
if (dp[0][i][j][k] >= dp[0][i - 1][f][j] + V[j][k]) {
dp[0][i][j][k] = dp[0][i - 1][f][j] + V[j][k];
dp[1][i][j][k] = dp[1][i - 1][f][j] | (1 << k);
if (i == n - 1 && Bit_Count(dp[1][i][j][k]) == n - 1) {
Min = Math.min(Min, dp[0][i][j][k]);
}
}
}
}
}
}
if(Min == INF) cout.println("0");
else cout.println(Min);
}
cout.flush();
}
}

• @ 2015-01-31 12:15:41

很模板的集合dp.
d[S][v]表示考虑部分玩家的集合S,并且物品从玩家v开始传.
边界 d[{v}][v]=0;
递推 d[S][v]=min( d[S\{v}][i] + cost[v][i] );
加一个记忆化.

程序比较丑=w=

## Code

int n;
int E[20][20];

inline int fullset()
{ return (1<<n)-1; }

inline int remove(int k,int S)
{ return S-(1<<k); }

inline bool exist(int k,int S)
{ return (S&(1<<k))!=0; }

inline int count(int S)
{ int res=0; for(int i=0;i<n;i++) res+=exist(i,S); return res; }

int d[65537][17];
int DFS(int S,int s)
{
if(d[S][s]!=-1) return d[S][s];
if(count(S)==1) return 0;

int res=INF;
for(int i=0;i<n;i++)
if(exist(i,S) && i!=s)
res=min(res,DFS(remove(s,S),i)+E[s][i]);

return d[S][s]=res;
}

int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
cin>>E[i][j];
if(E[i][j]==-1) E[i][j]=(1<<28)-1;
}

int res=INF;

for(int i=0,u=fullset();i<=u;i++)
for(int j=0;j<n;j++) d[i][j]=-1;

for(int i=0;i<n;i++)
res=min(res,DFS(fullset(),i));

cout<<res<<endl;

return 0;
}

• @ 2014-05-12 23:21:34

/*happywu
* 2014.5.12
*/
/*happywu
* 2014.5.12 */
状压+记忆化搜索
状态转移方程: f[p][i]=min(f[q][j]+map[j][i]); 状态q+第i个人的状态等于状态P

### Block code

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const ll Inf=(ll)1e9;
ll f[67000][18];
int n,map[20][20];
ll search(int p,int x)
{
if(f[p][x]!=-1)return f[p][x];
int q=p^(1<<(x-1));
ll ans=Inf,temp=Inf;
for(int i=1;i<=n;i++)
{
if(q&(1<<(i-1)))
temp=map[i][x]+search(q,i);
if(temp<ans)ans=temp;
}
f[p][x]=ans;
return ans;
}
int main()
{
//freopen("a.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&map[i][j]);
ll ans=Inf;
for(int i=1;i<=(1<<n);i++)
for(int j=0;j<=n;j++)
f[i][j]=-1;
for(int i=1;i<=n;i++)
f[1<<(i-1)][i]=0;

for(int i=1;i<=n;i++)
{
ll temp=search((1<<n)-1,i);
if(temp<ans)ans=temp;
}
printf("%lld\n",ans);
return 0;
}

• @ 2014-05-12 23:18:05

/*happywu
* 2014.5.12
*/
状压+记忆化搜索
状态转移方程: f[p][i]=min(f[q][j]+map[j][i]); 状态q+第i个人的状态等于状态P
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const ll Inf=(ll)1e9;
ll f[67000][18];
int n,map[20][20];
ll search(int p,int x)
{
if(f[p][x]!=-1)return f[p][x];
int q=p^(1<<(x-1));
ll ans=Inf,temp=Inf;
for(int i=1;i<=n;i++)
{
if(q&(1<<(i-1)))
temp=map[i][x]+search(q,i);
if(temp<ans)ans=temp;
}
f[p][x]=ans;
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&map[i][j]);
ll ans=Inf;
for(int i=1;i<=(1<<n);i++)
for(int j=0;j<=n;j++)
f[i][j]=-1;
for(int i=1;i<=n;i++)
f[1<<(i-1)][i]=0;

for(int i=1;i<=n;i++)
{
ll temp=search((1<<n)-1,i);
if(temp<ans)ans=temp;
}
printf("%lld\n",ans);
return 0;
}

• @ 2014-02-19 22:44:45

DP，F[K][I][J]，表示共传了K个，起点为I终点为J传的最小值。则类似FOLYED思想，用T枚举中转站，则只有2种情况转移：
F[K-1][I,T]+MAP[T,J]和F[K-1][T,J]+MAP[I,T];，因为可能转移会重复加入了某个点，所以这种DP是不可行的。怎么办呢？
则必须要用数组记录当前已经传了哪几个点，可是时间不允许。但如果用状态压缩呢，因为N只有16，如果去了1 5 2三个点，且转到了5，则可以用G[5][（11001）2]表示。每加入一个点G数组就+1《(x-1);

• @ 2013-10-20 23:30:35

我第一次居然用了integer
###
var
i,j,k,m,n:longint;
l,tt,t:longint;
ii,min:longint;
a,b,c:array[0..65536] of longint;
f:array[1..65536,1..16] of longint;
map:array[1..16,1..16] of longint;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do
inc(i);
while x<a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
y:=b[i];
b[i]:=b[j];
b[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;

if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
begin
m:=1;
for i:=1 to n do
m:=m*2;
dec(m);
for i:=1 to m do
begin
k:=0;
j:=i;
while j>0 do
begin
k:=k+j and 1;
j:=j shr 1;
end;
a[i]:=k;
b[i]:=i;
end;

sort(1,m);

fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=1 to n do

for i:=n+1 to m do
begin
for j:=1 to n do
begin
if ((b[i] shr (j-1)) and 1)=1 then
begin
t:=b[i] xor (1 shl (j-1));
min:=maxlongint;
for k:=1 to n do
if (((t shr (k-1)) and 1)=1) and (k<>j) then
if min>f[t][k]+map[k][j] then
begin
min:=f[t][k]+map[k][j];
end;
f[b[i]][j]:=min;
end;
end;
end;

min:=maxlongint;
for i:=1 to n do
if f[m][i]<min then min:=f[m][i];
writeln(min)
end.

• @ 2013-07-18 14:04:49

这就是一裸状压DP
可我的复杂度
2^n*n^2
?! 是不是太弱了

• @ 2009-11-09 09:48:52

用位运算压缩当前的状态，记录当前传到哪个人手上，用队列进行递推

• @ 2009-11-02 16:25:47

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 9ms

├ 测试数据 16：答案正确... 9ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 9ms

├ 测试数据 19：答案正确... 25ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：52ms

Vijos Easy

一次AC很爽

我承认我写得很诡异

用f表示状态为i，当前在第j点所能得到的最小值

i是用2进制表示的状态

初始化f[1 shl(i-1),i]=0

然后把所有的1 shl(i-1)存到一个队列里

就是记录当前已经扩展的状态

之后每次从队头拿一个状态出来

枚举i，j

其中i表示队头状态当前所到达的点

j表示从i出发走到的下一个点

i要走过，j不能走过（这个用位运算判断）

然后去更新状态

把新生成的状态加入到队尾

一直做到队列里面剩一个状态

也就是那个最后全部都走过的状态

最后输出f[1 shl n-1,i]的最大值

其实就是用宽搜生成状态然后进行dp

下面是主过程

fillchar(f,sizeof(f),\$7f);//初始化

fillchar(h,sizeof(h),0);//记录当前状态是否出现过的数组

for i:=1 to n do

begin

s[i]:=1 shl(i-1);

f[s[i],i]:=0;

h[s[i]]:=true;

end;

p:=1;q:=n;//初始队头队尾

while pf[s[p],i]+a then f[x,j]:=f[s[p],i]+a; //更新f数组

if not h[x] then //判断新状态是否出现过，没出现过就加入队尾

begin

h[x]:=true;

inc(q);

s[q]:=x;

end;

end;

inc(p);

end;

ID
1456

6

(无)

2135

581

27%

2