阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入 口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口 的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。 阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。 阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会积累Ai点疲劳值。阿明是工作狂， 他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。 【输入格式】 输入文件名为salesman.in。 第一行有一个正整数N，表示螺丝街住户的数量。 接下来的一行有N个正整数，其中第i个整数Si表示第i家住户到入口的距离。数据保证 S1≤S2≤…≤Sn<108。 接下来的一行有N个正整数，其中第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。 数据保证Ai<103。 【输出格式】 输出文件名为salesman.out。 输出 N 行，每行一个正整数，第 i 行整数表示当 X=i 时，阿明最多积累的疲劳值。
记忆化搜索加上状压DP。 上代码吧。。
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int f[15][1<<15]; int r[(1<<15)+1]; int w[15][15]; int inf=(1e9)+7; int min(int x,int y) { if(x<=y) return x; else return y; } int dfs(int u,int state) { //printf("%d %d\n",u,state); if(f[u][state]!=-1) return f[u][state]; int rstate=state&(~(1<<u)); // vis[u] = true; if(rstate==0) return f[u][state]=w[u][0]; int ans=inf; while(rstate) { int p=(rstate)&(-rstate); int v=r[p]; ans=min(ans,dfs(v,state&(~(1<<u)))+w[u][v]); rstate-=p; } return f[u][state]=ans; } int main() { freopen("salesman.in","r",stdin); freopen("salesman.out","w",stdout); int n; scanf("%d",&n); for (int i=0;i<=n;i++) for (int j=0;j<n;j++) scanf("%d",&w[i][j]); for (int i=0;i<= 15;i++) r[1<<i]=i; memset(f,-1,sizeof(f)); int lim=(1<<n)-1; printf("%d\n",dfs(0,lim)); return 0; }还算易懂的代码
