E - K-periodic Garland dp

题目传送门

以为数据到了1e6+就不能dp了，其实因为只有两种状态还是可以dp 的，我们设dp[i][0]为选到第i个元素的时候将其的状态设置为1，设dp[i][1]为选到第i个元素的时候将其状态设置为1，再运用一下前缀和，则可以将每一种情况都表示出来。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 5;
int dp[N][2];
int sum[N];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        
        int n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
        {
            dp[i][1] = dp[i][0] = sum[i] = 0;
        }
        string s = " ";
        string tmp;
        cin >> tmp;
        s += tmp;
        for (int i = 1; i <= n; i++)
        {
            int t = s[i] == '1';
            sum[i] = sum[i - 1] + t ;
        }
        for (int i = 1; i <= n; i++)
        {
            int t = s[i] == '1';
            int p = s[i] == '0';
            //状态转移方程
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][0]) + t;
            if (i <= k)
            {
                dp[i][1] = sum[i - 1] + p;
            }
            else
                dp[i][1] = min(sum[i - 1], dp[i - k][1] + sum[i - 1] - sum[i - k ]) + p;
        }
        int ans = min(dp[n][1], dp[n][0]);
        cout << ans << endl;
    }
    return 0;
}