题解

108 条题解

  • 2
    @ 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
    @ 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);
    }
    
  • 2
    @ 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

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

  • 1
    @ 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

  • 0
    @ 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;
    }
    
  • 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;
    }

  • 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;
    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
    @ 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;
    }
    
  • 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);
    }
    

    记忆化暴搜

  • 0
    @ 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
    @ 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;
    }

  • 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();
    }
    }

  • 0
    @ 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;
    }

  • 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;
    }

  • 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;
    }

  • 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);

  • 0
    @ 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
    @ 2013-07-18 14:04:49

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

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

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

  • 0
    @ 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
分类
动态规划 | 状态压缩DP 点击显示
标签
(无)
递交数
2031
已通过
548
通过率
27%
上传者