P1433 吃奶酪

状压DP。

初见：这不就是跟愤怒的小鸟和制作武器差不多吗？

（代码）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,lg;
double x[15],y[15],f[1<<15];
inline ll read(){
    ll x=0,f=0;
    char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}
inline double solve(ll u,ll v){
    double tot=0;
    tot=fabs(x[u]-x[v])*fabs(x[u]-x[v])+fabs(y[u]-y[v])*fabs(y[u]-y[v]);
    tot=sqrt(tot);
    return tot;
}
int main(){
    n=read();
    for(register int i=1;i<=n;++i)
        scanf("%lf%lf",&x[i],&y[i]);
    lg=1<<n;
    for(register int i=0;i<lg;++i)
        f[i]=(double)0x3f3f3f3f;
    for(register int i=1;i<=n;++i)
        f[1<<(i-1)]=solve(0,i);
    for(register int i=0;i<lg;++i)
        for(register int j=1;j<=n;++j)
            if(i&(1<<(j-1)))
                for(register int k=1;k<=n;++k)
                    if((k!=j)&&!(i&(1<<(k-1))))
                        f[i^(1<<(k-1))]=min(f[i^(1<<(k-1))],f[i]+solve(j,k));
    cout<<fixed<<setprecision(2)<<f[lg-1];
    return 0;
}

错法和这个题解一模一样（详情也参照题解）

（AC代码）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,lg,top,q[16];
double x[16],y[16],f[16][1<<16],ans;
inline ll read(){
    ll x=0,f=0;
    char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}
inline double solve(ll u,ll v){
    double tot=0;
    tot=fabs(x[u]-x[v])*fabs(x[u]-x[v])+fabs(y[u]-y[v])*fabs(y[u]-y[v]);
    tot=sqrt(tot);
    return tot;
}
int main(){
    memset(f,127,sizeof(f));
    n=read();
    for(register int i=1;i<=n;++i){
        scanf("%lf%lf",&x[i],&y[i]);
        f[i][1<<(i-1)]=solve(0,i);
    }        
    lg=1<<n;
    for(register int i=0;i<lg;++i){
        top=0;
        for(register int j=1;j<=n;++j)
            if(!(i&(1<<(j-1))))
                q[++top]=j;
        for(register int j=1;j<=n;++j)
            if(abs(f[j][i]-f[0][0])>=0.0000001)
                for(register int k=1;k<=top;++k)
                    f[q[k]][i^(1<<(q[k]-1))]=min(f[q[k]][i^(1<<(q[k]-1))],f[j][i]+solve(q[k],j));
    }        
    ans=f[0][0];
    for(register int i=1;i<=n;++i)
        ans=min(ans,f[i][lg-1]);
    printf("%.2lf\n",ans);
    return 0;
}

double赋最大值就赋$127$

值得注意的是，ans如果赋值成$127$会错一个点？

经测试，$f[0][0]$的值确实要比$127$大很多

memset(f,127,sizeof(f));

这条语句中$f$数组被赋值成为了1.38242e+306