我看到这些翻转的题就怕，可能要练下这些专题。

我最怕这类题了。

一开始想了下dp， dp[i][0 / 1]表示完成了前i位，第i位不按 / 按，的状态，然后发现转移不了。无果。好像是按下这一位，然后后面的k个又会变，表示不了。

然后来了一个贪心，对于第1个，在[1, k + 1]之间，肯定要按下一个了，那么按哪一个呢？我自己写了一个函数来判断按下这一个位的价值，就是，[pos - k, pos + k]数中所有的和，然后按下了这位，就跳去下一个没亮的区间按，然后这个有反例。

7 2

1 0 500 1 100000 0 100000

 

然后就觉得自己做不出了，看到别人那里说，按下的灯应该间隔2 * k。也就是不应该有重叠，枚举k + 1个区间就好。

想想还真有道理。无奈想不到。

#include 
      
       #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;const int maxn = 1e6 + 20;int a[maxn];LL sum[maxn];void work() {    int n, k;    scanf("%d%d", &n, &k);    for (int i = 1; i <= n; ++i) scanf("%d", a + i);    for (int i = 1; i <= n; ++i) {        sum[i] = sum[i - 1] + a[i];    }    LL ans = 1e18;    for (int i = 1; i <= min(n, k + 1); ++i) {         LL t = 0;        for (int j = i; j <= n; j = j + 2 * k + 1) {            t += a[j];            if (j + 2 * k + 1 > n && j + k < n) {                t = 1e18;                break;            }        }        ans = min(ans, t);    }    cout << ans << endl;}int main() {#ifdef local    freopen("data.txt", "r", stdin);//    freopen("data.txt", "w", stdout);#endif    work();    return 0;}
      

7 9

1 1 500 1 100000 1 100000