首页 > 代码库 > 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;}