PKU_campus_2018

PKU_campus_2018_A Wife

思路：

题目链接http://poj.openjudge.cn/practice/C18A/

先说一个结论，每一天要么7要么0，由此提供一种状态压缩dp的解法。

实现：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 10005, INF = 0x3f3f3f3f;
 4 int a[MAXN], dp[2][1 << 7];
 5 int main()
 6 {
 7     int t, n;
 8     cin >> t;
 9     while (t--)
10     {
11         cin >> n;
12         int msk = (1 << 7) - 1;
13         memset(dp, 0x3f, sizeof dp);
14         for (int i = 1; i <= n; i++) cin >> a[i];
15         for (int i = 0; i < 1 << 7; i++) dp[0][i] = 0;
16         for (int i = 0; i < n; i++)
17         {
18             memset(dp[i + 1 & 1], 0x3f, sizeof dp[i + 1 & 1]);
19             for (int j = 0; j < 1 << 7; j++)
20             {
21                 int tmp = j << 1 & msk;
22                 dp[i + 1 & 1][tmp | 1] = min(dp[i + 1 & 1][tmp | 1], 
23                                              dp[i & 1][j] + 7 * a[i + 1]);
24                 if (i >= 6 && !tmp) continue;
25                 dp[i + 1 & 1][tmp] = min(dp[i + 1 & 1][tmp], dp[i & 1][j]);
26             }
27         }
28         int minn = INF;
29         for (int i = 1; i < 1 << 7; i++) minn = min(minn, dp[n & 1][i]);
30         cout << minn << endl;
31     }
32     return 0;
33 }