首页 > 代码库 > hdu 3237
hdu 3237
dp 状态压缩
#include <cstdio>#include <cstdlib>#include <cmath>#include <map>#include <set>#include <queue>#include <stack>#include <vector>#include <sstream>#include <string>#include <cstring>#include <algorithm>#include <iostream>#define maxn 105#define INF 0x3f3f3f3f#define inf 10000000#define MOD 100000000#define ULL unsigned long long#define LL long longusing namespace std;int hi[maxn], dp[2][maxn][1<<9][10], n, m, one[1<<9], mh, begin;int countone(int x) { int ans = 0; for(int i = 0; i < 8; ++ i) if(x&(1<<i)) ans ++; return ans;}void init() { begin = mh = 0; for(int i = 0; i < (1 << 8); ++ i) { one[i] = countone(i); }}int main(){ int ca = 0; init(); while(scanf("%d%d", &n, &m) == 2 && n+m) { // printf("ff: %d\n", num); begin = mh = 0; for(int i = 0; i < n; ++ i) { scanf("%d", &hi[i]); hi[i] -= 25; mh = max(hi[i], mh); begin |= (1 << hi[i]); } mh ++; int tot = 1<<mh; for(int i = 0; i <= m; ++ i) { for(int j = 0; j < tot; ++ j) { for(int k = 0; k <= mh; ++ k) { dp[0][i][j][k] = INF; } } } dp[0][0][1<<hi[0]][hi[0]] = 1; dp[0][1][0][mh] = 0; int now, pre; for(int i = 1; i < n; ++ i) { now = i%2; pre = 1-now; for(int j = 0; j <= m && j <= i+1; ++ j) { for(int k = 0; k < tot; ++ k) { for(int q = 0; q <= mh; ++ q) { dp[now][j][k][q] = INF; } } } for(int j = 0; j <= m && j <= i; ++ j) { for(int k = 0; k < tot; ++ k) { for(int q = 0; q <= mh; ++ q) { if(dp[pre][j][k][q] == INF) continue; int nowk = k|(1<<hi[i]); if(j < m) dp[now][j+1][k][q] = min(dp[now][j+1][k][q], dp[pre][j][k][q]); if(hi[i] == q) { dp[now][j][k][q] = min(dp[now][j][k][q], dp[pre][j][k][q]); } else { dp[now][j][nowk][hi[i]] = min(dp[now][j][nowk][hi[i]], dp[pre][j][k][q]+1); } } } } } int ans = n; for(int i = 0; i <= m; ++ i) { for(int j = 0; j < tot; ++ j) { for(int k = 0; k < mh; ++ k) { int st = begin^j; ans = min(ans, one[st]+dp[now][i][j][k]); } } } printf("Case %d: %d\n\n", ++ca, ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。