SRM 483 div1 med: Bribes
解法
influence の値はたかだか 500 なので, now 番目の人は, now+8 番目までの人にしか影響は及ぼしません。
そこで, dp[now][state] = (now 番目の人で, now-8 番目から now+7 番目の人への賄賂を送ったか送ってないかのフラグが state で表されるような状態における, 残りの人に賄賂を送らなければならない人数の最小数)
とします。
now 番目の人が投票してくれるなら, now+8 番目の人に賄賂を送るかどうかはどちらでも良いですが, now 番目の人が投票してくれない状態の時は, now+8 番目の人に賄賂を送って resistance を下げる必要がある, というように遷移していきます。
now == n-8 の時は, now 〜 n-1 番目の人が投票してくれるかを判定して, 投票してくれないなら INF を, そうでないなら 0 を返します。
const int INF = 1e9; int dp[55][1<<16]; vector<int> influence, resistance; int dfs(int now, int state) { int& ret = dp[now][state]; if (ret >= 0) return ret; int n = influence.size(); if (now+8 >= n) { for (int i = now; i < n; i++) { int tmp = resistance[i]; for (int j = 0; j < 16; j++) { if ((state>>j)&1) { int eff = influence[now+j-8]; tmp -= eff>>(abs(i-(now+j-8))); } } if (tmp > 0) return ret = INF; } return ret = 0; } int tmp = resistance[now]; for (int i = 0; i < 16; i++) { if ((state>>i)&1) { int eff = influence[now+i-8]; tmp -= eff>>(abs(8-i)); } } ret = INF; if (tmp <= 0) { ret = min(ret, dfs(now+1, state>>1)); ret = min(ret, 1+dfs(now+1, (state>>1)|(1<<15))); } else { if (tmp-(influence[now+8]>>8) <= 0) ret = min(ret, 1+dfs(now+1, (state>>1)|(1<<15))); } return ret; } class Bribes { public: int minBribes(vector <int> influence, vector <int> resistance) { ::influence = influence; ::resistance = resistance; int n = influence.size(); if (n < 8) { int ans = INF; for (int s = 0; s < (1<<n); s++) { vector<int> tmp = resistance; for (int i = 0; i < n; i++) { if ((s>>i)&1) { for (int j = 0; j < n; j++) { tmp[j] -= influence[i]>>(abs(i-j)); } } } bool ng = false; for (int i = 0; i < n; i++) if (tmp[i] > 0) ng = true; if (!ng) ans = min(ans, __builtin_popcount(s)); } if (ans >= INF) ans = -1; return ans; } else { memset(dp, -1, sizeof(dp)); int ans = INF; for (int s = 0; s < (1<<8); s++) { ans = min(ans, __builtin_popcount(s) + dfs(0, s<<8)); } if (ans >= INF) ans = -1; return ans; } } };