C - Cent Savings UVALive - 6952

2023-11-09 14:58
文章标签 cent uvalive savings 6952

本文主要是介绍C - Cent Savings UVALive - 6952,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

注意动态规划的思路 就是由各个状态递推到下一个状态

规定dp【i】【j】为 第i跟数分割为j块

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int dp[2200][22];
int sum[2200];
int a[2200];
int main()
{int n,d;while(~scanf("%d%d", &n, &d)){memset(dp,0,sizeof(dp));memset(sum,0,sizeof(sum));memset(a,0,sizeof(a));for(int i = 1; i <= n; i++){scanf("%d", &a[i]);sum[i]=sum[i-1]+a[i];}for(int i = 1; i <= n; i++){for(int j = 1; j <= d; j++)dp[i][j] = INF;}for(int i = 1; i <= n; i++)if(sum[i]%10 >= 5)dp[i][0] = sum[i]/10*10+10;elsedp[i][0] = sum[i]/10*10;for(int i = 1; i <= d; i++){dp[0][i] = 0;}for(int i = 1; i <= n; i++){for(int j = 1; j <= d; j++){for(int k = 1; k < i; k++)//有前面的状态递推过来{int to = sum[i] - sum[k];if(to % 10 >= 5){    to = to/10*10+10;dp[i][j] = min(dp[i][j], dp[k][j-1]+to);}else{to = to/10*10;dp[i][j] = min(dp[i][j], dp[k][j-1] + to);}}}}int ans = INF;for(int i = 0; i <= d; i++){ans = min(ans, dp[n][i]);}printf("%d\n",ans);}
}


这篇关于C - Cent Savings UVALive - 6952的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/376822

相关文章

【UVALive】6709 Mosaic 二维线段树

传送门:【UVALive】6709 Mosaic 题目大意: 每次选择矩阵中的一个点,求以他为中心,边长为D(D一定是奇数)的矩阵中的最小值min和最大值max,输出ans =(min+max)/ 2(向下取整)。然后将该点的值修改为ans。 题目分析: 赤果果的二维线段树单点修改、区间查询。 又一次学习了线段树,发现原来所有的更新操作全部放在二维中即可。 很不错,一定要经常看看,温

【UVALive】3887 Slim Span 枚举+最小生成树

传送门:【UVALive】3887 Slim Span 题目大意:给出一个n(2 <= n <= 100)个结点的无向图,找一棵苗条度(最大边减最小边的值)最小的生成树。图中不含自环或重边。 题目分析:枚举最小边求生成树即可。模板用用萌萌哒~ 代码如下: #include <cstdio>#include <cstring>#include <algorit

【UVALive】5713 Qin Shi Huang's National Road System 最小生成树

传送门:【UVALive】5713 Qin Shi Huang's National Road System 题目大意:秦朝有n个城市,需要修建一些道路使得任意两个城市之间都可以连通。道士徐福声称他可以用法术修路,不花钱,也不用劳动力,但只能修一条路,因此需要慎重选择用法术修哪一条路。秦始皇不仅希望其他道路的总长度B尽量短(这样可以节省劳动力),还希望法术连接的两个城市的人口之和A尽量大,因此下

【UVALive】3661 Animal Run 平面图最小割 最短路

传送门:【UVALive】3661 Animal Run 题目大意:给你一个n*m个点的网格图,其中动物园在左上角,动物们的目的地在右下角,现在你需要派出一些工作人员拦截某些边使得没有一只动物能到达右下角,已知每个单元网格中存在左上角到右下角的对角线,网格中的边以及对角线都是双向的,每条道路有个权值,表示拦截这条边所需要的工作人员数。你的任务是派尽量少的工作人员使得达到目的。 题目分析

【UVALive】2965 Jurassic Remains 中途相遇法

传送门:【UVALive】2965 Jurassic Remains 题目分析:本题用了一个很不错的思想——中途相遇法。 因为题目的数据很小,我们很容易想到暴力,但是2^24次方的枚举依旧复杂度太大,因此我们可以这么做:将一半的串枚举异或能得到的所有的值,插入到map中,然后再枚举异或另一半的串能得到的所有的值,然后查找map中的与这个值相同的有没有,更新一下能得到的最大数量即可。 成

【UVALive】6163 Myth Busters 类24点

传送门:【UVALive】6163 Myth Busters 题目分析: 可以使用括号,还有加减乘除,问能否用四个0~9的数凑出10。。。我了个去。。渣渣不会写拿来当模拟写了,写的人都要吐了。。。。 先处理出所有两个数和起来的情况,然后用两个数和起来的情况再加上一个数处理出所有三个数和起来的情况,最后用两个两个数或者一个三个数加一个数的继续推出四个数的,最后按照不降序保存。 这个能一

UVALive 4255 Guess

题意: 给你半个矩阵  如果(i,j)的位置是'-'  则说明sum[i...j]<0  如果是'+'  说明sum>0  如果是'0'  说明sum=0  给出一种满足这个矩阵的序列  序列元素绝对值在10以内 思路: 很容易想到的是将sum[i...j]转化为sum[j]-sum[i-1]  即用前缀和来表示  那么题中的矩阵就可以转化成前缀和之间的大小比较  也就是说  我们可以通过

UVALIVE 5000 Underwater Snipers(二分+贪心)

二分答案 贪心判断 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <iostream>#include <iomanip>#include <cstring>#include <climits>#include <comple

UVALIVE 4887 Soccer UVELIVE 4882

2015 UESTC Winter Training #6 训练赛的两道搜索模拟题 uvalive 4882 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <iostream>#include <iomanip>#include

HDU 5150 UVALive 5061 (LCA标记)

这两题都是在树上求某一些路径上的点权的变化 两道题的思路相同 HDU 5150: 每一种颜色我们分开考虑他们对所有节点的贡献,对于颜色同为c的两个节点u和v(假设u!=v),那么在lca(u,v)的时候我们需要-1,因为在lca(u,v)一直到根的路径上,颜色c只能影响一次。基于此,我们对每种颜色的所有节点按照dfs序排好序,首先每个节点+1,然后对dfs序相邻的两个节点(注意颜色要相同)求