动态规划bzoj1584[usaco2009mar]cleaningup打扫卫生

关键词：

Description

Input

Output

Sample Input

Sample Output

11

神奇的dp题，懒得写题解了，贴个链接

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int n,m,nn;
 8 int a[40010],f[40010],pre[40010],pos[40010],cnt[40010];
 9 int main()
10 {
11     scanf("%d%d",&n,&m);
12     nn=int(sqrt(n));
13     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
14     for(int i=0;i<=n;i++) f[i]=i;
15     memset(pre,-1,sizeof(pre));
16     for(int i=1;i<=n;i++){
17         for(int j=1;j<=nn;j++) 
18             if(pre[a[i]]<=pos[j]) cnt[j]++;
19         pre[a[i]]=i;
20         for(int j=1;j<=nn;j++) 
21             if(cnt[j]>j){
22                 int tmp=pos[j]+1;
23                 while(pre[a[tmp]]>tmp) tmp++;
24                 pos[j]=tmp;
25                 cnt[j]--;
26             }
27         for(int j=1;j<=nn;j++) f[i]=min(f[i],f[pos[j]]+j*j);
28     } 
29     printf("%d
",f[n]);
30     return 0;
31 }

bzoj1584:[usaco2009mar]cleaningup打扫卫生

【算法】DP+数学优化【题意】把n个1~m的数字分成k段，每段的价值为段内不同数字个数的平方，求最小总价值。n,m,ai<=40000【题解】参考自：WerKeyTom_FTD令f[i]表示把前i个数分成若干段的最小价值。转移中我们定义，从i开始往前... 查看详情

[bzoj1584][usaco2009mar]cleaningup打扫卫生（dp）

传送门 不会啊，看了好久的题解才看懂TT因为可以直接分成n段，所以就得到一个答案n，求解最小的答案，肯定是<=n的，所以每一段中的不同数的个数都必须<=sqrt(n)，不然就不是最小的答案 那么f[i]表示前i个数的最有... 查看详情

bzoj1584

1584:[Usaco2009Mar]CleaningUp打扫卫生TimeLimit:10Sec  MemoryLimit:64MBSubmit:467  Solved:316[Submit][Status][Discuss]Description有N头奶牛，每头那牛都有一个标号Pi，1<=Pi<=M<=N<=40000。现在Farm 查看详情

[bzoj3398][usaco2009feb]bullcow牡牛和牝牛（动态规划）

3398:[Usaco2009Feb]Bullcow牡牛和牝牛TimeLimit: 1Sec  MemoryLimit: 128MBSubmit: 235  Solved: 159[Submit][Status][Discuss]Description    约翰要带N(1≤N≤ 查看详情

动态规划bzoj1575:[usaco2009jan]气象牛baric(代码片段)

预处理普通动态规划；庆祝1A三连Description为了研究农场的气候,Betsy帮助农夫John做了N(1<=N<=100)次气压测量并按顺序记录了结果M_1...M_N(1<=M_i<=1,000,000).Betsy想找出一部分测量结果来总结整天的气压分布.她想用K(1<=K<=N)个... 查看详情

[bzoj3399][usaco2009mar]sandcastle城堡（排序）

3399:[Usaco2009Mar]SandCastle城堡TimeLimit: 3Sec  MemoryLimit: 128MBSubmit: 79  Solved: 66[Submit][Status][Discuss]Description约翰用沙子建了一座城堡．正如所有城堡的城墙，这城墙也有许多枪眼，两个相邻 查看详情

bzoj3401[usaco2009mar]lookup仰望*

bzoj3401[Usaco2009Mar]LookUp仰望题意：约翰的N头奶牛站成一排，奶牛i的身高是Hi。对于奶牛i，如果奶牛j满足i<j且Hi<Hj，我们可以说奶牛i可以仰望奶牛j。求出每只奶牛离她最近的仰望对象。n≤100000.题解：用一个单调栈维护即可... 查看详情

bzoj3399[usaco2009mar]sandcastle城堡（贪心）

 【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3399 【题目大意】　　　将一个集合调整成另一个集合中的数，把一个数+1需要消耗x，-1需要消耗y，问最小消耗。 【题解】　　显然两个集合排序之后一一对应... 查看详情

bzoj3399[usaco2009mar]sandcastle城堡：贪心最小匹配代价

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3399题意：　　给你一个数列a，和一个可变换顺序的序列b（数列长度≤25000）。　　a增加一个单位代价为x，降低一个单位代价为y。　　求a变为b的最小代价。 题解：　　贪心... 查看详情

洛谷p2904[usaco08mar]跨河rivercrossing动态规划

洛谷P2904[USACO08MAR]跨河RiverCrossing动态规划区间DPf[i]表示将i头牛运了过去，然后John又返回所需要的最少时间 1#include<cstdio>2#include<cstring>3#include<cmath>4#include<cstdlib>5#include<string>6#in 查看详情

bzoj1585:[usaco2009mar]earthquakedamage2地震伤害

【题意】给定无向图，现在可能有一些点已经被删除，只给出信息是c个点未被删除且不能到达结点1，求最少的删除点个数。【算法】最小割【题解】本题和1的区别是：1求的是最少的不能到达1的结点数，那么就把损坏点圈缩在... 查看详情

bzoj1585:[usaco2009mar]earthquakedamage2地震伤害

n<=3000个点m<=20000条无向边的图，有p<=n个出发点，每个出发点都不可拆，现拆一些点使每个出发点都不能到达点1，求最小点数。简单的最小割。每个点拆成两个x和y，无向边A--B即Ay->Bx,By->Ax，每个点拆成的x和y再连边容... 查看详情

bzoj(begin)1375[usaco2009mar]cowfrisbeeteam奶牛沙盘队：dp和为f的倍数

题目链接：http://begin.lydsy.com/JudgeOnline/problem.php?id=1375题意：　　给你n个数，你可以从中选任意多个，但不能不选。问你所选数字之和为f的倍数的方案数。 题解：　　表示状态：　　　　dp[i][j]=numofways　　　　i：考虑到第i... 查看详情

[bzoj3371][poj2009][usaco2004mar]moouniversity-emergencypizzaorder定制比萨饼

标题这么长的。。真是让感觉人头大脚轻。这道题我并没有A,拿到了80pts。做法基于二分图匹配但还包含贪心。很玄乎，给大家提供思路而已。贴题面先。 Description    Moo大学的餐厅必须为$C(1leq Cleq 1000)$... 查看详情

bzoj1571[usaco2009open]滑雪课ski

...送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1571【题解】动态规划，设f[i,j]表示第i天能力值为j最多滑几个坡可以不滑、选个耗时最小的破滑（预处理），或者学习。复杂度O(TS*100)可以把那个S优化掉。#include<stdio.h>#include<str... 查看详情

bzoj1700[usaco2007jan]problemsolving解题动态规划

【BZOJ1700】[Usaco2007Jan]ProblemSolving解题Description过去的日子里,农夫John的牛没有任何题目.可是现在他们有题目,有很多的题目.精确地说,他们有P(1<=P<=300)道题目要做.他们还离开了农场并且象普通人一样找到了工作.他们的月薪是M(... 查看详情

bzoj1571:[usaco2009open]滑雪课ski

【算法】动态规划【题解】yy出了O(1wlog1w)的算法。将雪坡排序预处理出g[i]表示能力值为i的最短时长雪坡。这样就可以定义work(t,c)表示时长t能力c的最多滑雪数量,work(t,c)=t/g[c]。然后将课程按结束时间排序。f[i]=f[j]+work(a[i].begin-a[j]... 查看详情

bzoj15849.20考试cleaningup打扫卫生

1584:[Usaco2009Mar]CleaningUp打扫卫生TimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 549  Solved: 382[Submit][Status][Discuss]Description有N头奶牛，每头那牛都有一个标号Pi，1<=Pi<= 查看详情