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)美元．每个干草公司的货源都十分充足，可以卖出无限多的干草包． 帮助约翰找到最小的开销来满足需要，即采购到至少H磅干草． Input …

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]; for ( int i = 1 ; i <= n ; i++) { dp[i] = 1; for ( int j = 1 ; j < i ; j++) { if (a[i]>a[j]) dp[i] = max(dp[i],dp[j]+1); } ans = max(ans,dp[i]); } 然后我们发现，使得dp[i]得到同一个值的dp[j]可能有多 …

题目链接 题意：给出n个点，m条边，定义一条路径的价值为【路径长度*(路径终点的度)】，求最大价值。 思路：一月份的时候写过一个回溯。。。TLE22了。。。其实也能猜到是dp..但是无奈不会写。然而其实真的不难== 我们枚举路径的终点，dp[i]表示以点i为终点能得到的最长路径长度。 转移方程：dp[i] = max(dp[i],dp[edge[i][j]]+1); 含义是与i点相连的j点是否要将i点加在以j点为路径末尾的路径的终点，使i点成为新的路径终点。 具体看代码 /* *********************************************** Author :111qqz Created Time …

题目链接 题意：设条件A为一个数恰好是k个互不相同的b的整数次幂的和，问某一个区间内满足条件A的数的个数是有多少个。 Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2: 17 = 24+20, 18 = 24+21, 20 = 24+22. 思路：数位dp..需要理解清楚恰好有k个b的互不相同的整数次幂的和这句话。 如果恰好是b的整数幂。。可以转化成b进制。。 互不相同。。说明。。所有位置上的数字要么是0，要么是1. 于是题目可以转化成求某区间内，满足一 …

题目链接s 题意：将一个10进制数x按照2进制展开后得到的值设为f(x)...现在给出a,b（10^9）问【0，b】中满足f[x]<=f[a]的数的个数。 思路：先算出f[a]...然后我们发现f(x)最大也就10*2^10=10240.。。数组可以存下。。搞之。和上一道题类似。。我们不关心两个f函数的值具体是多少。。。只关心他们的相对大小情况。。所以还是可以合并成一个变量。。。然而我用两个变量为什么错了。。不懂== 错误代码（用两个变量分别记录） /* *********************************************** Author :111qqz Created Time :2016年03月17 …

hdu5642题目链接 题意：问长度为n的仅由26个小写字母组成的合法字符串有多少个。如果某个字符连续出现四次或以上，则这个字符串为非法。否则为合法。 思路：当时以为是组合数学的题。。。推了半天公式还是还是gg... 现在学了数位dp..果然是数位dp里很简单的一种。。。 dp[i][j][k]表示长度为i,最后一个字符对应的数字为j,最后一个字符出现了k次的方案数。 需要注意的是，这种连续几个位置相等或者不相等什么的。。。没有必要维护具体那些位置上的字符是什么。。。所以这种只统计最后一个字符，以及最后一个字符出现的次数的方法具有普遍意义。。注意理解。。。