108 条题解
-
2
zyc2000 LV 9 @ 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 -
2
#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); } -
2
很水的状压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; }-
maxiaodan @ 2017-10-18 16:51:09
哎，蒟蒻写了一节课，还调了一节课，向大佬低头
-
-
1
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
-
0
#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; } -
0
MichaelKnight LV 4 @ 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;
} -
0
一开始直接就是打的搜索，过了九个点，￣へ￣
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;
inline int read()
{
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()
{
n=read();ans=inf;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=read();
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;
inline int read()
{
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()
{
n=read();ans=inf;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
v[i][j]=read();
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;}
-
0
//就是要提醒一下，一定要注意括号，一不小心就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; } -
0
#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); }记忆化暴搜
-
0
lemontree712 LV 10 @ 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;
} -
0
#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;
} -
0
经典的状态压缩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();
}
} -
0
很模板的集合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;
} -
0
/*happywu
* 2014.5.12
*/
/*happywu
* 2014.5.12 */
状压+记忆化搜索
状态转移方程: f[p][i]=min(f[q][j]+map[j][i]); 状态q+第i个人的状态等于状态PBlock 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;
} -
0
/*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;
} -
0
williamking5 LV 8 @ 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
readln(n);
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
read(map[i][j]);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. -
0
编译通过...
├ 测试数据 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 有效耗时：52msVijos 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;
zyc2000
LV 9
@ 2018-02-24 21:04:52
