[SGU 183] Painting the balls

一、题目

来源不详，好像是个外国网站。

$peter$ 把 $n$ 个白球排成一列，他想把一些白球刷为黑色，且任意连续 $m$ 个球中至少要有 $2$ 个黑球，$peter$ 知道他需要 $C_i$ 的燃料刷第 $i$个球，你的任务是找出 $peter$ 所需的最少的燃料达到目标。

$2\le n\le 10^4,2\le m\le 100,m\le n$

二、解法

数据范围已经给出了很明显的提示了，设$dp[i][j]$为最后两个球染了$i$和$i?j$，$[1,i]$全部合法的方案数，转移考虑让$i?1$这个位置结尾的$m$段合法，那么：
dp[i][j]=min?{dp[i?j][k]+a[i]}k∈[1,m?j]dp[i][j]=\min\{dp[i-j][k]+a[i]\}\space k\in[1,m-j]dp[i][j]=min{ dp[i?j][k]+a[i]} k∈[1,m?j]不难发现可以用前缀和优化。初始化我们要处理$1\le i,j\le m$的情况，如果状态$dp[i][j]$满足$m?(i?j)<n$就可以计入答案，时间复杂度$O(nm)$

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 10005;
int read()
{
    int num=0,flag=1;char c;while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar();return num*flag;
}
int n,m,ans=1e9,a[M],dp[M][105],g[M][105];
signed main()
{
    n=read();m=read();for(int i=1;i<=n;i++)a[i]=read();memset(g,0x3f,sizeof g);memset(dp,0x3f,sizeof dp);for(int i=1;i<=m;i++)for(int j=1;j<i;j++){
    dp[i][j]=a[i]+a[i-j];g[i][j]=min(g[i][j-1],dp[i][j]);if(n-(i-j)<m) ans=min(ans,dp[i][j]);}for(int i=m+1;i<=n;i++)for(int j=1;j<m;j++)/*for(int k=1;k<=m-j;k++){dp[i][j]=min(dp[i][j],dp[i-j][k]+a[i]);if(n-(i-j)<m) ans=min(ans,dp[i][j]); }*/{
    dp[i][j]=g[i-j][m-j]+a[i];g[i][j]=min(g[i][j-1],dp[i][j]);if(n-(i-j)<m) ans=min(ans,dp[i][j]);}printf("%d\n",ans);
}
/* i-j dp[i][j]=dp[i-j][ [1,m-j] ] + c[i] */