sgu 183. Painting the balls 动态规划 难度:3
2024-10-11 22:10:56
183. Painting the balls
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
memory limit per test: 4096 KB
input: standard input
output: standard output
output: standard output
Petya puts the N white balls in a line and now he wants to paint some of them in black, so that at least two black balls could be found among any M successive balls. Petya knows that he needs Ci milliliters of dye exactly to paint the i-th ball. Your task is to find out for Petya the minimum amount of dye he will need to paint the balls.
Input
The first line contains two integer numbers N and M (2<=N<=10000, 2<=M<=100, M<=N). The second line contains N integer numbers C1, C2, ..., CN (1<=Ci<=10000).
Output
Output only one integer number - the minimum amount of dye Petya will need (in milliliters).
Sample test(s)
Input
6 3
1 5 6 2 1 3
1 5 6 2 1 3
Output
9
Note
Example note: 1, 2, 4, 5 balls must be painted.
思路:dp[i][j]//在i染色,在i-j染色的最小花费 设a b更新到,a b c,由远(距a m-1距c 1)到近以b为中心更新dp即可
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10001;
const int maxm=101;
const int inf=1e9+5;
int dp[maxn][maxm];//back maxm
int c[maxn];
int n,m;
int main(){
while(scanf("%d%d",&n,&m)==2){
//memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)scanf("%d",c+i);
for(int i=0;i<m;i++){
for(int j=0;j<i;j++){
dp[i][i-j]=c[i]+c[j];//g[i-j]=min(dp[i][j],g[i-j]);
}
}
for(int j=1;j<n;j++){
int minn=inf;
for(int i=min(n,j+m)-1;i>j&&i>=m;i--){
minn=min(dp[j][m+j-i],minn);
dp[i][i-j]=minn+c[i];
}
}
int ans=inf;
for(int i=n-m+1;i<n;i++){
for(int j=min(m-1,i-n+m);j>0;j--)
ans=min(ans,dp[i][j]);
}
printf("%d\n",ans);
}
return 0;
}
最新文章
- idea初使用之配置使用maven仓库
- Kindle DXG和Win10 64bits无法连接的问题
- php面试题之五——PHP综合应用(高级部分)
- Uva 12361 File Retrieval 后缀数组+并查集
- jdk1.7升级到jdk1.8后出错: [ERROR] javadoc: warning - Multiple sources of package comments found for package
- Linux kernel ‘aac_send_raw_srb’函数输入验证漏洞
- Asp.net Mvc 自定义Session (二)
- linux ptheard 生产者消费者
- Android Layout Binder(在线将XML中View find出来,生成java代码的工具)
- 聊一聊JQ中delegate事件委托的好处
- 简陋的 ASP.NET CORE 单页Web应用程序“框架”
- 洛谷 P1226 【模板】快速幂||取余运算
- 20190412 T-SQL语言一
- 教你怎么上传本地代码到github
- 好习惯: 用controller as 语法和$inject数组注入
- 简单实用UML关系图解
- ActionBarSherlock(一)在Eclipse中如何引入ActionBarSherlock和它的例子?
- 编译可移植的python
- 多播知识by 陈胜君
- redis源码学习_整数集合
热门文章
- [c/c++]指针(2)
- <;OFFER05>; 05_ReplaceSpaces
- Linux 安装、启动和卸载SSH
- Educational Codeforces Round 56 (Rated for Div. 2)
- 编译安装lamp (php)
- Linux批量更改文件后缀-转载
- python 文件分割
- 文件上传allowedTypes和文件下载contentType(mimeType)
- 《剑指offer》第十七题(打印1到最大的n位数)
- Android提高第九篇之GridView和SQLite实现分页表格