本文主要是介绍lightoj 1037 - Agent 47 （状压DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：你现在需要消灭n个敌人，n个敌人的血量已知，你的普通攻击力为1，但是如果你杀死敌人i可以用它的武器去杀死其他敌人，p[i][j] 表示用敌人i的武器射杀敌人j会减p[i][j]滴血.问你最少可以攻击多少次可以将敌人杀死。
思路:
定义集合s为死亡敌人的集合。
dp[s] 为让集合为s的人死亡最小需要的攻击次数。
如果现在想要消灭敌人i 并且敌人i不属于s
那么dp[s | (1<<i)] = min(dp[s|(1<<i)] , dp[s] + t);
t 为用死亡敌人的武器消灭敌人i的最小费用。如何求t成为了本题的关键。
考虑死亡敌人集合s，你同样也拥有了死亡敌人j的武器【j属于集合s】
那么t = min(t, 用敌人j 的武器射杀i的次数) 【j属于集合s】
当t一次都没有被更新时，说明死亡敌人的武器没有可以消灭敌人i的，只能用普通武器攻击
/************************************************ Author: fisty* Created Time: 2015-08-20 11:16:46* File Name : 1037.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define lson l, m, k<<1
#define rson m+1, r, k<<1|1
#define MAX_N 16
int t;
int n;
int target[MAX_N]; //目标i 的血量
int p[MAX_N][MAX_N]; //p[i][j]武器i 对 敌人j 的 伤害
int dp[1<<MAX_N];
void solve(){Memset(dp, 0x3f);dp[0] = 0;for(int s = 0;s < (1<<n)-1; s++){for(int i = 0;i < n; i++){if(!(s&(1<<i))){int t = INF; //把第i个人杀死需要多少次for(int j = 0;j < n; j++){if(s & (1<<j) && p[j][i] != 0){int k; //用第j个武器杀第i个人需要多少次int m = target[i] / p[j][i];k = (target[i] % p[j][i]) ? m+1 : m;t = min(t, k);}}if(t == INF) t = target[i]; //如果不能用敌人的武器杀，只有用攻击力为1的武器杀dp[s|(1<<i)] = min(dp[s|(1<<i)], dp[s] + t); }}}printf("%d\n", dp[(1<<n)-1]);
}
int main(){//freopen("in.cpp", "r", stdin);//cin.tie(0);//ios::sync_with_stdio(false);scanf("%d", &t);int cnt = 1;while(t--){scanf("%d", &n);for(int i = 0;i < n; i++){scanf("%d", &target[i]);}string s[MAX_N];for(int i = 0;i < n; i++){cin >> s[i]; }for(int i = 0;i < n; i++){for(int j = 0;j < n; j++){p[i][j] = s[i][j]-'0';//Debug(p[i][j]);}}printf("Case %d: ", cnt++);solve();}return 0;
}
这篇关于lightoj 1037 - Agent 47 （状压DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
