1632: [Usaco2007 Feb]Lilypad Pond
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 496 Solved: 153 [Submit][Status][Discuss]
Description
Farmer John 建造了一个美丽的池塘，用于让他的牛们审美和锻炼。这个长方形的池子被分割成了 M 行和 N 列( 1 ≤ M ≤ 30 ; 1 ≤ N ≤ 30 ) 正方形格子的 。某些格子上有惊人的坚固的莲花，还有一些岩石，其余的只是美丽，纯净，湛蓝的水。 贝茜正在练习芭蕾舞，她从一个莲花跳跃到另一个莲花，当前位于一个莲花。她希望在莲花上一个一个的跳，目标是 …
阅读更多1618: [Usaco2008 Nov]Buying Hay 购买干草
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 906 Solved: 456 [Submit][Status][Discuss]
Description
约翰的干草库存已经告罄，他打算为奶牛们采购日(1≤日≤50000)磅干草．
他知道N(1≤N≤100)个干草公司，现在用1到N给它们编号．第i个公司卖的干草包重量为Pi(1≤Pi≤5000)磅，需要的开销为Ci(l≤Ci≤5000)美元．每个干草公司的货源都十分充足，可以卖出无限多的干草包． 帮助约翰找到最小的开销来满足需要，即采购到至 …
阅读更多1617: [Usaco2008 Mar]River Crossing渡河问题
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 837 Solved: 606 [Submit][Status][Discuss]
Description
Farmer John以及他的N(1 <= N <= 2,500)头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。 由于奶牛不会划船，在整个渡河过程中，FJ必须始终在木筏上。在这个基础上，木筏上的奶牛数目每增加1，FJ把木筏划到对岸就得花更多的时间。 当FJ一个人坐在木筏上，他把木筏划到对岸需要M(1 <= M <= …
阅读更多1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1012 Solved: 553 [Submit][Status][Discuss]
Description
奶牛们在被划分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上游走，试图找到整块草地中最美味的牧草。Farmer John在某个时刻看见贝茜在位置 (R1, C1)，恰好T (0 < T <= 15)秒后，FJ又在位置(R2, C2)与贝茜撞了正着。 FJ并不知道在这T秒内贝茜是否曾经 …
阅读更多1613: [Usaco2007 Jan]Running贝茜的晨练计划
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1468 Solved: 706 [Submit][Status][Discuss]
Description
奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行N(1 <= N <= 10,000)分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。 贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第i分钟内跑步，她可以在这一分钟内跑D_i(1 <= D_i <= 1,000)米，并且她的疲 …
阅读更多首先回顾一下n^2的做法。 状态转移方程为dp[i] =max(1,dp[j]) (1=<j<=i-1&&a[i]>a[j])
for ( int i = 1 ; i <= n ; i++) cin>>a[i];1 for ( int i = 1 ; i <= n ; i++) 2 { 3 dp[i] = 1; 4 for ( int j = 1 ; j < i ; j++) 5 { 6 if (a[i]>a[j]) 7 dp[i] = max(dp[i],dp[j]+1); 8 } 9 …
阅读更多hdu5642题目链接 题意：问长度为n的仅由26个小写字母组成的合法字符串有多少个。如果某个字符连续出现四次或以上，则这个字符串为非法。否则为合法。
思路：当时以为是组合数学的题。。。推了半天公式还是还是gg... 现在学了数位dp..果然是数位dp里很简单的一种。。。 dp[i][j][k]表示长度为i,最后一个字符对应的数字为j,最后一个字符出现了k次的方案数。
阅读更多