[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\in [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]
*/