题解 P4962 【朋也与光玉】

蒟蒻的首道状压题... 太蒟蒻，下面有些概念很可能会说的不准确。。。 这个程序可能算记忆化搜索的解法？（我还是觉得叫它剪枝搜索更直观。） 跑的出乎意料的快，吸氧总时间在720ms到790ms波动，最慢点170ms~180ms，不吸氧1100ms左右，考场上卡了我很久的#8这样剪枝之后用10ms就过了...（可能是数据比较适合这样写）~~（乱搞碾标算）~~ 比赛时的最优解，管理员神犇出现后的次优解(tql QAQ)。 时间复杂度：**O(玄学)** （理论上界应该很惨，但是基本上不可能达到，所以貌似没法算？）~~（能算也不会算，我太蒻了）~~ ```cpp #include <iostream> using namespace std; #define I_MAX 2147483647 const int kmaxn=100+5; int point[kmaxn];//该点颜色 int map[kmaxn][kmaxn];//邻接矩阵 int cut[32767+5][kmaxn];//cut[状态][当前位置]表示记录每个情况的最优解 int ans=I_MAX,n,m,k; int u,v,w; void dfs(int status,int pos,int dest,int deepth=1)//status的每个二进制位表示是否拿了这种光玉 { if((status>>point[pos])&1||ans<=dest||(cut[status][pos]!=0&&cut[status][pos]<=dest))//拿过的光玉重复或不可能是最优解，那就不走 return; if(deepth>=k)//都取完了，更新答案 { ans=min(ans,dest);//其实min没啥用，上面的if剪枝保证了dest<ans（刚发现） return; } cut[status][pos]=dest;//这应该属于记忆化吧，反正我是用来剪枝了，毕竟这个dfs函数没有返回值 status+=1<<point[pos];//更新当前状态 for(register int i=1;i<=n;++i)//遍历出边 { if(map[pos][i])dfs(status,i,dest+map[pos][i],deepth+1);//能走就试着走 } } int main() { ios::sync_with_stdio(false); cin>>n>>m>>k; for(register int i=1;i<=n;++i) { cin>>point[i]; } for(register int i=0;i<m;++i) { cin>>u>>v>>w; map[u][v]=w;//m最大为n(n-1)，很适合邻接矩阵存边 } for(register int i=1;i<=n;++i) { dfs(0,i,0);//从每个点开始搜 } if(ans==I_MAX) { cout<<"Ushio!"<<endl; } else { cout<<ans<<endl; } return 0; } ``` 这篇题解只说记忆化（剪枝？），不写递推，因为我不会。。。。 最近爆了好几场0，明天还要期中考试，希望写个题解能rp++;~~也希望管理员给个通过。~~