本文共 1296 字,大约阅读时间需要 4 分钟。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 //#include 9 //#include 10 //#include 11 #define LL long long12 13 using namespace std;14 //using namespace __gnu_pbds;15 16 int dp[1<<20];17 18 int attack[20][20],health[20];19 20 int n;21 22 int check(int j,int i)23 {24 int a = 1;25 a = max(a,attack[j][i]);26 return (health[i]/a) + (health[i]%a?1:0);27 }28 29 int dfs(int statu)30 {31 if(dp[statu] != -1)32 return dp[statu];33 dp[statu] = 0x3f3f3f3f;34 if(statu == 0)35 return dp[statu] = 0;36 for(int i = 1; i <= n; i++)37 {38 if( ((statu>>(i-1))&1) == 0 )39 continue;40 dp[statu] = min(dp[statu],dfs( (statu^(1<<(i-1))))+health[i]/1);41 for(int j = 1; j <= n; j++)42 {43 if(i == j) continue;44 45 if( ((statu>>(j-1))&1) == 0)46 {47 dp[statu] = min(dp[statu],dfs( (statu^(1<<(i-1)) )) + check(j,i) );48 }49 }50 51 }52 53 return dp[statu];54 }55 56 void solve()57 {58 memset(dp,-1,sizeof(dp));59 60 scanf("%d",&n);61 for(int i = 1; i <= n; i++)62 scanf("%d",&health[i]);63 for(int i = 1; i <= n; i++)64 for(int j = 1; j <= n; j++)65 scanf("%1d",&attack[i][j]);66 67 int ans = dfs( (1<
转载于:https://www.cnblogs.com/henserlinda/p/5743699.html