Five in a Row, Again-记录状态的dfs+剪枝

本文主要是介绍Five in a Row, Again-记录状态的dfs+剪枝，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

用一个二进制记录当前状态。

二进制中的0代表当前点已经被走过，1代表当前点还未走过。

如果当前二进制之前计算过，且值大于当前值的话，那么就终止不走。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int shuyu[5001];
int n;
int w[101][101];
int e[101][101];
int s[101];
int dp[5001];
void init()
{int ns=1;for(int i=1;i<=12;i++){shuyu[ns]=i;ns=ns*2;}for(int i=1;i<=5000;i++)if(shuyu[i]==0)shuyu[i]=shuyu[i-1];
}
void dos(int num,int exp,int as)
{//cout<<num<<" "<<exp<<" "<<as<<endl;if(num<dp[as])return ;dp[as]=num;if(as==0)return;int st;st=as;int ed;ed=as;while(ed){st=ed&(ed-1);st=ed-st;int pp=shuyu[st];if(exp>s[pp])dos(num+w[1][pp],exp+e[1][pp],as-(1<<(pp-1)));else dos(num,exp+e[1][pp],as-(1<<(pp-1)));ed=ed-st;}
}
int main()
{int _,i,j;init();scanf("%d",&_);while(_--){memset(dp,0,sizeof(dp));scanf("%d",&n);for(i=1;i<=n;i++){for(j=1;j<=n;j++){scanf("%d",&e[i][j]);}}for(i=1;i<=n;i++){for(j=1;j<=n;j++){scanf("%d",&w[i][j]);}}for(i=1;i<=n;i++){scanf("%d",&s[i]);}int as=0;int ns=1;for(i=1;i<=n;i++){as+=(1<<(i-1));}as-=1;int leap=1;int ans=0;while(leap){leap=0;for(i=2;i<=n;i++){if(s[1]<=s[i])continue;if((1<<(i-1))&as){s[1]+=e[1][i];as-=(1<<(i-1));ans+=w[1][i];leap=1;}}}if(as==0)cout<<ans<<endl;else{dp[as]=ans;dos(ans,s[1],as);cout<<dp[0]<<endl;}}
}

这篇关于Five in a Row, Again-记录状态的dfs+剪枝的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---