Educational Codeforces Round 109 (Rated for Div. 2)

D. Armchairs
比赛时以为贪心可以做。。。其实是一个dp

代码

 1 int a0[N],a1[N];
 2 int dp[N][N];
 3 int main()
 4 {
 5     ios::sync_with_stdio(false); cin.tie(nullptr);
 6     
 7     int n;
 8     cin >> n;
 9     int cnt0 = 0, cnt1 = 0;
10     for (int i = 1; i <= n; i++) {
11         int tmp;
12         cin >> tmp;
13         if (tmp) {
14             a1[++cnt1] = i;
15         }
16         else
17             a0[++cnt0] = i;
18     }
19     for (int i = 1; i <= cnt1; i++) {
20         for (int j = i; j <= cnt0; j++) {
21             if (j == i) {
22                 dp[i][j] = dp[i - 1][j - 1] + abs(a1[i] - a0[j]);
23             }
24             else
25                 dp[i][j] = min(dp[i - 1][j - 1] + abs(a1[i] - a0[j]),
26                     dp[i][j - 1]);
27         }
28     }
29     
30     cout << dp[cnt1][cnt0];
31 }