欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[SGU 183] Painting the balls

程序员文章站 2022-07-02 11:30:56
一、题目来源不详,好像是个外国网站。peterpeterpeter 把 nnn 个白球排成一列,他想把一些白球刷为黑色,且任意连续 mmm 个球中至少要有 222 个黑球,peterpeterpeter 知道他需要 CiC_iCi​ 的燃料刷第 iii个球,你的任务是找出 peterpeterpeter 所需的最少的燃料达到目标。2≤n≤104,2≤m≤100,m≤n2\leq n\leq10^4,2\leq m\leq 100,m\leq n2≤n≤104,2≤m≤100,m≤n二、解法数据范围...

一、题目

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

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

2 ≤ n ≤ 1 0 4 , 2 ≤ m ≤ 100 , m ≤ n 2\leq n\leq10^4,2\leq m\leq 100,m\leq n 2n104,2m100,mn

二、解法

数据范围已经给出了很明显的提示了,设 d p [ i ] [ j ] dp[i][j] dp[i][j]为最后两个球染了 i i i i − j i-j ij [ 1 , i ] [1,i] [1,i]全部合法的方案数,转移考虑让 i − 1 i-1 i1这个位置结尾的 m m m段合法,那么:
d p [ i ] [ j ] = min ⁡ { d p [ 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[ij][k]+a[i]} k[1,mj]不难发现可以用前缀和优化。初始化我们要处理 1 ≤ i , j ≤ m 1\leq i,j\leq m 1i,jm的情况,如果状态 d p [ i ] [ j ] dp[i][j] dp[i][j]满足 m − ( i − j ) < n m-(i-j)<n m(ij)<n就可以计入答案,时间复杂度 O ( n m ) O(nm) 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]
*/ 

本文地址:https://blog.csdn.net/C202044zxy/article/details/109261264

相关标签: dp 1024程序员节