题目链接
题意
\(N\) 种气体,\(i\) 气体与 \(j\) 气体碰撞会:
产生 \(a[i][j]\) 的威力;
导致 \(j\) 气体消失
求产生威力之和的最大值
思路
\(dp[state][p]\) 表示 \(p\) 气体消失后到达 \(state\) 时的威力最大值
注意: 与前几题 图上的问题 不同,\(i\) 与 \(p\) 气体碰撞导致 \(p\) 气体消失, 并不意味着上一个消失的气体是 \(i\) 气体
所以搜索时应该使用二重循环进行枚举: 一重枚举碰撞的气体, 另一重枚举上一个消失的气体
- Code
- #include <bits/stdc++.h>
- #define F(i, a, b) for (int i = (a); i < (b); ++i)
- #define F2(i, a, b) for (int i = (a); i <= (b); ++i)
- #define dF(i, a, b) for (int i = (a); i > (b); --i)
- #define dF2(i, a, b) for (int i = (a); i >= (b); --i)
- #define maxn 10
- #define maxs 1100
- using namespace std;
- typedef long long LL;
- int n, dp[maxs][maxn], dis[maxn][maxn];
- bool vis[maxs][maxn];
- int dfs(int state, int p) {
- if (state==(1<<p)) return 0;
- if (vis[state][p]) return dp[state][p];
- vis[state][p] = true;
- int sta = state-(1<<p), ans=0;
- F(i, 0, n) {
- if (i==p || !(state&(1<<i))) continue;
- int temp = dfs(sta, i);
- F(j, 0, n) {
- if (j==p || !(state&(1<<j))) continue;
- ans = max(ans, temp+dis[j][p]);
- }
- }
- return dp[state][p] = ans;
- }
- void work() {
- memset(dis, 0, sizeof dis);
- memset(dp, 0, sizeof dp);
- memset(vis, 0, sizeof vis);
- F(i, 0, n) {
- F(j, 0, n) {
- scanf("%d", &dis[i][j]);
- }
- }
- int ans = 0;
- F(i, 0, n) ans = max(ans, dfs((1<<n)-1, i));
- printf("%d\n", ans);
- }
- int main() {
- while (scanf("%d",&n)!=EOF&&n) work();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2499738.html