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

你哥我淪落到開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;
}