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; }

　　

转载于:https://www.cnblogs.com/avema/p/3863738.html

总结

以上是生活随笔为你收集整理的hdu 3237的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。