改變我的代碼風格的確是一件非常困難的事情

你哥我淪落到開vpn來上blogger了,杯具啊!
最近做狀壓動規做上癮了.hdu3920.一看就知道這不是個禿論.
方程:dp[s|(1<<i)|(1<<j)]=dp[s]+min(cost(i,j));
注意幾點
1.顯然當確定要消去i點和j點的時候,就應該貪心地先消去里起始點最近的點
2.轉移時可以限制i是按照標號順序可以被消去的第一個點,然後直接只枚舉j.這樣狀態不會減少,轉移複雜度大大減少.
3.這狀態轉移方程的拓撲關係比較混亂,所以可以根據這個轉移方程建立一個有向圖然後廣搜一遍.
source code:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
using namespace std;
#define maxn 21
#define clr(a) memset(a,0,sizeof(a))
#define inf (1000000000)
const int maxs=(1<<20);
struct point{
  double x,y;
};
point p[maxn];
point st;
double dp[maxs];
int q[maxs+2];
double tmpd;
int testcase,ff,rr,n,s;
inline double sqr(double a){
  return a*a;
}
inline double dis(point a,point b){
  return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
bool compare(const point &a,const point &b){
  return dis(st,a)<dis(st,b);
}
int main(){
  freopen("in.txt","r",stdin);
  scanf("%d",&testcase);
  for(int ttestcase=1;ttestcase<=testcase;++ttestcase){
    printf("Case #%d: ",ttestcase);
    scanf("%lf%lf",&st.x,&st.y);
    scanf("%d",&n),n+=n;
    for(int i=0;i<n;i++)
      scanf("%lf%lf",&p[i].x,&p[i].y);
    sort(p,p+n,compare);
    s=(1<<n);
    for(int i=1;i<s;i++)
      dp[i]=inf;
    dp[0]=0,ff=1,rr=0,q[1]=0;
    for(int tmp,i,j,tmps;rr<ff;){
      tmp=q[++rr];
      for(i=0;i<n;i++)
        if(!(tmp&(1<<i)))
          break;
      for(j=i+1;j<n;j++)
        if(!(tmp&(1<<j))){
          tmps=(tmp|(1<<i)|(1<<j));
          tmpd=dp[tmp]+dis(st,p[i])+dis(p[i],p[j]);
          if(dp[tmps]>tmpd){
            if(dp[tmps]>=inf)
              q[++ff]=tmps;
            dp[tmps]=tmpd;
          }
        }
    }
    printf("%.2lf\n",dp[s-1]);
  }
  fclose(stdin);
  return 0;
}