hdu2018题目链接

题意:第1年有1头奶牛，每年生一头奶牛，新生的奶牛从生下来的第四年（包括生下来那年）也开始每年一头奶牛。 问第n年有多少头奶牛。 思路：最容易想到的。。递推一下。。。dp[i] = dp[i-1] + dp[i-3] (注意初始化不是一个dp[1]=1,而是dp[1..4]=1..4)

hdu2084题目链接

题意：dp入门题。。。数字三角形。。

思路：

昨天看mit公开课。。。讲到dp的精髓是sub-problem+ reuse…

为什么自底向上呢。。。

初始化dp[n][i] = a[n][i]其实是在处理只有最后一行的子问题。。。

hdu 4283题目链接

题意：有N个人按顺序排成一排上台表演，每个都有一个num[]值，若在他是第k个上场的人，则会有num[]*(k-1)的unhappiness。台下有一个黑屋（stack），对每一个人，可以选择让他先进屋子或者直接上台。现在让你找到一个最优方案使得所有人的unhappiness之和最小。

poj 3661题目链接

题意：锻炼，一共n分钟，每分钟可以选择跑步或者休息，第i分钟跑步可以跑d[i]米，并增加一点疲劳度，如果选择休息，那么每分钟减少1点疲劳值。一旦开始休息，必须休息到疲劳值为0才能再次开始跑步。疲劳值不能超过m.第n分钟的时候疲劳值必须为0，否则之后会感觉身体被掏空。问n分钟最远多多远。

poj 1651题目链接

题意：n个数，删掉a[i]的得分是a[i]*a[i-1]*a[i+1]，两个端点的不允许删。问删完n-2个数得到的最小分数是多少。

poj 3280 题目链接

题意：一个字符串，给出添加一个字符或者删掉该字符的花费，问最小的话费使得字符串变成回文串。

思路：dp[i][j]表示区间[i,j]的字符串变成回文的最小花费。。。

light oj 1422 题目链接

题意：

按顺序去参加舞会。每个舞会对衣服都有要求。可以连续穿好多件衣服。需要时候就脱下来，但是一旦脱下来，这件衣服就报废了。问最少需要几件衣服。

poj2955题目链接

题意：给出若干括号，问最大匹配数是多少。

思路：没有思路。我知道这是dp。。。然后其他就什么都不知道了。。。转移方程？ 完全没思路。。知道了转移方程。。。。嗯，还是不会。。。边界怎么写？状态怎么推？循环顺序? 循环次序？我一点思路都没有。。。。。

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 504  Solved: 265 [Submit][Status][Discuss]

Description

The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget. The roller coaster will be built on a long linear stretch of land of length L (1 …

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 451  Solved: 226 [Submit][Status][Discuss]

Description

考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了’x’。例如下图：

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])

 1for ( int i = 1 ; i <= n ; i++) cin>>a[i];
 2
 3	for ( int i = 1 ; i <= n ; i++)
 4	{
 5	    dp[i] = 1;
 6	    for ( int j = 1 ; j < i ; j++)
 7	    {
 8		if (a[i]>a[j])
 9		    dp[i] = max(dp[i],dp[j]+1);
10	    }
11 …

比赛链接

两题QAQ

A：7分钟1A 有n个大人m个小孩乘公交车，票价每人一元，一个大人最多免费带一个小孩，没有大人陪同的小孩不能乘车。 问是否有解，如果有解输出所有乘客付的钱的可能的最小值和可能的最大值。

题目链接 题意：给出n个点，m条边，定义一条路径的价值为【路径长度*(路径终点的度)】，求最大价值。 思路：一月份的时候写过一个回溯。。。TLE22了。。。其实也能猜到是dp..但是无奈不会写。然而其实真的不难== 我们枚举路径的终点，dp[i]表示以点i为终点能得到的最长路径长度。

题目链接 题意：设条件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:

题目链接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函数的值具体是多少。。。只关心他们的相对大小情况。。所以还是可以合并成一个变量。。。然而我用两个变量为什么错了。。不懂==