数据 enter 能够 sam src max spa 参加
Input
Output
Sample Input
- 5 4 PHPP PPHH PPPP PHPP PHHP
Sample Output
- 6
这两天室友和几个同系的同学都去参加了北大 ACM 暑期学校,借着这个光,我也跟着看北大老师的 ppt 和做相应题目学习了一个。
其实这道题本身对于我还是有些挑战性的,看了 ppt 中讲解的思路,就豁然开朗了。
用 dp[i][j][k] 记录第 i 行状态为 j,第 i-1 行状态为 k 的最大炮兵部队摆放个数。
dp[i][j][k] = max{dp[i-1][k][m], m = 0...1023} + Num(j),
在不优化时一行的状态数有 2^10=1024 个,可是注意到其中许多是显然不符合题意的。故需要预处理一下,将不符合的直接去掉,通过简单的 DFS 就可以得出总共恰好有 60 种情况。(注意一行什么都不填也是一种)这是本题非常重要的突破点,通过这个时间复杂度就降了下来。
接下来还需要对第一行的情况特殊处理一下,然后就依照上述状态转移方程进行下去就可以了。
(NOI 题目 ac 数 ++ ~~)
- 1#include 2#include < string > 3#include 4#include 5#include 6#include 7#include 8#include < set > 9#include 10#include 11#include 12#include 13#define mp make_pair 14 //#define P make_pair
- 15#define MIN(a, b)(a > b ? b: a) 16 //#define MAX(a,b) (a>b?a:b)
- 17 typedef long long ll;
- 18 typedef unsigned long long ull;
- 19 const int MAX = 110;
- 20 const int INF = 1e8 + 5;
- 21 using namespace std;
- 22 //const int MOD=1e9+7;
- 23 typedef pairint > pii;
- 24 const double eps = 0.00000001;
- 25 //map<int,int>id_code,id_num;
- 26 int id_code[70],
- id_num[70];
- 27 int cnt,
- ge;
- 28 void dfs(int code, int lo, int num) 29 {
- 30
- for (int i = lo + 3; i < 10; i++) 31 {
- 32 dfs(code | (1 < 1); 33
- }
- 34 id_num[cnt] = num;
- 35 id_code[cnt++] = code;
- 36
- }
- 37 int dp[MAX][70][70];
- 38 int n,
- m;
- 39 char tem[15];
- 40 int code;
- 41 int an;
- 42 bool check(int x, int y) //摆法x和地形y是否冲突
- 43 {
- 44 int legal = x & y; //摆上且符合地形的部分
- 45 int illegal = x ^ legal; //摆上且不符合地形的部分
- 46
- if (illegal) 47
- return false;
- 48
- return true;
- 49
- }
- 50 int main() 51 {
- 52
- for (int i = 0; i < 10; i++) 53 dfs(1 < 1);
- 54 memset(dp, 0, sizeof(dp));
- 55 id_num[cnt] = 0;
- 56 id_code[cnt++] = 0;
- 57
- while (~scanf("%d%d", &n, &m)) 58 {
- 59 code = 0;
- 60 an = 0;
- 61 scanf("%s", tem);
- 62
- for (int j = 0; j) 63
- if (tem[j] == 'P') 64 code |= (1 << j);
- 65
- for (int r = 0; r //特殊处理第一行
- 66 {
- 67
- if (check(id_code[r], code)) //这一行可以这么摆,与地形不冲突
- 68 {
- 69
- for (int p = 0; p) 70 {
- 71
- if (id_code[r] & id_code[p]) 72
- continue;
- 73 dp[0][r][p] = id_num[r]; //第一行的炮兵最多个数至于这一行怎么摆有关
- 74
- }
- 75
- }
- 76
- }
- 77
- for (int i = 1; i) 78 {
- 79 code = 0;
- 80 scanf("%s", tem);
- 81
- for (int j = 0; j) 82
- if (tem[j] == 'P') 83 code |= (1 << j);
- 84
- for (int r = 0; r) 85 {
- 86
- if (check(id_code[r], code)) //这一行可以这么摆,与地形不冲突
- 87 {
- 88
- for (int p = 0; p) 89
- for (int q = 0; q //前两行状态
- 90 {
- 91
- if ((id_code[p] & id_code[q]) || (id_code[r] & id_code[p]) || (id_code[r] & id_code[q])) //冲突则
- 92
- continue;
- 93 dp[i][r][p] = max(dp[i][r][p], dp[i - 1][p][q] + id_num[r]);
- 94
- }
- 95
- }
- 96
- }
- 97
- }
- 98
- for (int i = 0; i) 99
- for (int j = 0; j) 100 an = max(an, dp[n - 1][i][j]);
- 101 printf("%d\n", an);
- 102
- }
- 103
- return 0; 104
- }
(状压 dp)NOI 2001(POJ 1185) 炮兵阵地
来源: http://www.bubuko.com/infodetail-2217645.html