http://codeforces.com/gym/100676

題目大意是告訴你要修n門課，每門課有一個權值w[i], 在第k天修該課程講獲得k*w[i]的學習點數，給出了課程與先修課程的關系，要修該課程必須修完先修課程。問最多能學到多少點數。

非常簡單的一道狀壓dp(一開始我還誤導隊友寫成兩維的去了 T^T);

dp[s] : s 的二進制存放的是已經選擇的課程，在該狀態下的能獲得的最大的點數。

這時如果再學一門課程k，將轉移到狀態ss (s | (1 << k) ) ，能否轉移需要判斷合法性。這里把課程k的先修課程存在一個int里面，S & prev[k] ==?prev[k]則表示可以選項k課程。dp數組一開始需要初始化成無窮小。最后只要找dp[(1 << n ) - 1] 。

/*輸入真惡心*/

?

#include <map> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm>using namespace std;const int INF = 999999999;int n,m;map<string, int> Map;int w[20];int prve[20];void read() {cin >> n >> m;getchar();char _a[101];string _s, _t;int _num;int _len;for (int i=0; i<n; i++) {gets(_a);_len = strlen(_a);int k = 0;while(_a[k] < '0' || _a[k] > '9') k++;_a[k-1] = '\0';_s = (string) _a;_num = 0;while (k < _len && _a[k] >= '0' && _a[k] <= '9') {_num = _num * 10 + _a[k] - '0';k++;}Map[_s] = i;w[i] = _num;}for (int i=0; i<m; i++) {gets(_a);int k = 0;while (_a[k] != '-') k++;_a[k-1] = '\0';_s = (string) _a;_t = (string) (_a + k + 4);prve[Map[_t]] |= (1 << Map[_s]);} }int dp[(1<<18)+5];void DP () {for (int s=0; s<(1<<n); s++) {int _num = 0;for (int i=0; i<n; i++) {_num += ((s >> i) & 1);}for (int i=0; i<n; i++) {int ss = s | (1 << i);if (((s >> i & 1) != 0) || ((s & prve[i]) != prve[i])) continue;if (_num == 0 && prve[i] == 0) {dp[ss] = w[i];continue;}dp[ss] = max(dp[ss], dp[s] + (_num + 1) * w[i]);}}cout << dp[(1<<n)-1] << endl; }void init() {Map.clear();fill(dp, dp + (1 << 18), -INF);memset(prve, 0, sizeof(prve)); }int main () {int t;cin >> t ;while (t--) {init();read();DP();}return 0; } View Code

?

轉載于:https://www.cnblogs.com/xuelanghu/p/4483206.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的Codeforces Gym 100676G Training Camp 状压dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。