题目链接

题意：问长度为n，每个位置由且仅有‘H’和'T'组成的序列中，至少有连续k个‘H’出现的方案数。

思路：不会做，参考了题解 不过没有完全搞懂。

题目链接

题意：n个数，分成若干段，每段的代价为 ，求最小代价。

思路：dp。

状态方程很显然个鬼。。。

dp[i] 表示处理完前面i个数的最小代价。

dp[0] = 0 ;

dp[i] = min(dp[j]+(sum[i]-sum[j])^2) ( 0<j <i),sum[i]为a[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 题目链接

题意：

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

poj 1141题目链接

题意：给出一个括号序列，要求添加最少的括号，使得这个序列变成合法的括号匹配，输出最后的序列。

思路：区间dp。。。有了那么一点思路。。。我们可以用dp[i][j]表示区间[i,j]的序列最少需要添加几个符号使得匹配。。转移的话。。。和之前差不多。。dp[i][j] = dp[i+1][j-1] (s[i]与s[j])匹配。。。不匹配的话也是找中间某个点。。。初始化的话。。要变成最大值。。。比较没思路的是输出括号序列这部分。。。

poj2955题目链接

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

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

1652: [Usaco2006 Feb]Treats for the Cows

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

Description

FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he …