Mayflyyh
Mayflyyh
MayFlyyh's Blog

DP
文章归档

51nod 1294 修改数组

题意:给出一个整数数组A,你可以将任何一个数修改为任意一个正整数,最终使得整个数组是严格递增的且均为正整数。问最少需要修改几个数? n<=100000,0<=a[i]<=10^9 因为新生成的数列必须是正整数,那么第一个数必至少为1,同样,每个数在新生成的数…

   897   2018-10-23 去围观

BZOJ 2091 [Poi2010]The Minima Game

Description 给出N个正整数,AB两个人轮流取数,A先取。每次可以取任意多个数,直到N个数都被取走。 每次获得的得分为取的数中的最小值,A和B的策略都是尽可能使得自己的得分减去对手的得分更大。 在这样的情况下,最终A的得分减去B的得分为多少。 Input …

   208   2018-09-20 去围观

BZOJ 3875 [Ahoi2014&Jsoi2014]骑士游戏

Description 【故事背景】 长期的宅男生活中,JYY又挖掘出了一款RPG游戏。在这个游戏中JYY会 扮演一个英勇的骑士,用他手中的长剑去杀死入侵村庄的怪兽。 【问题描述】 在这个游戏中,JYY一共有两种攻击方式,一种是普通攻击,一种是法术攻 击。两种攻击…

   148   2018-09-20 去围观

BZOJ 1584 [Usaco2009 Mar]Cleaning Up 打扫卫生

有N头奶牛,每头那牛都有一个标号Pi,1 <= Pi <= M <= N <= 40000。现在Farmer John要把这些奶牛分成若干段,定义每段的不河蟹度为:若这段里有k个不同的数,那不河蟹度为$k*k$。那总的不河蟹度就是所有段的不河蟹度的总和。 求最小不和谐度哇 考…

   138   2018-08-16 去围观

BZOJ 4033 [HAOI2015]树上染色

有一棵点数为N的树,树边有边权。给你一个在0~N之内的正整数K,你要在这棵树中选择K个点,将其染成黑色,并 将其他的N-K个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。 问收益最大值是多少。 设dp[i][j]为以i为子树…

   267   2018-08-16 去围观

HDU 5603 D Game

给一个公差集合{D},再给N个数 1.在当前剩下的有序数组中选择X(X>=2) 个数字 2.检查1选择的X个数字是否构成等差数列,且公差∈{D} ; 3.如果2满足,删除这X个数字 4.重复1-3,直到不能删除更多数字 问最多可以删除多少个数字? N<=300 …

   162   2018-08-16 去围观

LOJ #539「LibreOJ NOIP Round #1」旅游路线

T 城是一个旅游城市,具有n个景点和m条道路,所有景点编号为 1,2,...,n。每条道路连接这n个景区中的某两个景区,道路是单向通行的。每条道路都有一个长度。 为了方便旅游,每个景点都有一个加油站。第i个景点的加油站的费用为 pi,加油量为ci。若汽车在第i个景点加…

   243   2018-08-16 去围观

POJ 1239-Increasing Sequences

有一串数字,在它们之间加逗号来分隔,使之成为一个上升序列。 要求最后一个数尽可能的小,如果有多个满足要求,则使第一个数尽可能大;如果还有多个,则使第二个最大,依此类推。 感觉这是一道很经典的线性DP题(因为做的太少了)。 思路就是首先保证后一个数尽…

   484   2018-07-15 去围观

BZOJ 1079[SCOI2008]着色方案

1079: [SCOI2008]着色方案 Time Limit: 10 Sec Memory Limit: 162 MB Description   有n个木块排成一行,从左到右依次编号为1~n。你有k种颜色的油漆,其中第i种颜色的油漆足够涂ci个木块。 所有油漆刚好足够涂满所有木块,即c1+c2+...+ck=n。相邻两…

   1,777   2018-07-12 去围观

bzoj 1233[Usaco2009Open]干草堆tower

1233[Usaco2009Open]干草堆tower Description 为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡 。一共有N大包的干草(1<=N<=100000)(从1到N编号)依靠传送带连续的传输进牛棚来。第i包干草有一个 宽度W_i(1<=w_i<=1…

   183   2018-05-16 去围观
加载更多