本文出自 &&http://blog.csdn.net/shuangde800
刘汝佳《算法竞赛入门经典-训练指南》的动态规划部分的习题Beginner &打开
这个专题一共有25题，刷完后对dp的感觉提升了不少。
现把解题报告整理了一下，希望对大家能有帮助。
入门习题 （Exercises: Beginner）
Partitioning by Palindromes
Wavio Sequence
可以转化为经典问题，时间O(nlogn)
Fewest Flops
序列划分模型；状态设计
Palindromic Subsequence
可以转化为LCS
Cellular Network
需要一点概率知识和推理
Mega Man's Missions
基础的集合动态规划
Joseph问题的变形
Martian Mining
模型简单，但需要减少重复计算
Paths through the Hourglass
类似01 背包问题
Headmaster's Headache
集合动态规划
Strategic Game
树上动态规划（基础题）
String Compression
字符串动态规划
Dance Dance Revolution
以跳舞机为背景的题目
Twenty Questions
有趣的问题；比较基础的动态规划
(extra)UVa10163
Storage Keepers
(extra)UVa10453
Make Palindrome
*(extra)UVa10254
The Priest Mathematician
**(extra)UVa437
The Tower of Babylon
**(extra)UVa442
Matrix Chain Multiplication
最优矩阵乘法
**(extra)UVa473
Raucous Rockers
**(extra)UVa590
Always on the Run
**(extra)UVa607
Scheduling Lectures
**(extra)UVa662
**(extra)UVa672
11584&-&Partitioning
by Palindromes&&&题解
1424&-&Salesmen&题解
10534&-&Wavio
Sequence&&题解
11552&-&Fewest
Flops&&题解
11404&-&Palindromic
Subsequence&&&&题解
1456&-&Cellular
Network& &&题解
11795&-&Mega
Man's Mission&&题解
1452&-&Jump&&题解&
1366&-&Martian
Mining &&题解
10564&-&Paths
through the Hourglass&&题解
10817&-&Headmaster's
Headache&&题解
1292&-&Strategic
game&&题解
1351&-&String
Compression&&题解
1291&-&Dance
Dance Revolution&& &&题解&
1252&-&Twenty
Questions&&题解
10163&-&Storage
Keepers&&题解
10453&-&Make
Palindrome&& &题解
10254&-&The
Priest Mathematician&&题解
Tower of Babylon& &题解
442&-&Matrix
Chain Multiplication& &题解
473&-&Raucous
Rockers&&题解
590&-&Always
on the run&&题解
607&-&Scheduling
Lectures&题解
662&-&Fast
Food&&题解
672&-&Gangsters&&题解
&此文从网络中自动搜索生成，不代表本网站赞成被搜索网站的内容或立场
&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 22:17:32
软件世界网- &2014 蜀ICP备号 三峰网旗下网站&此题卡了我一下午一直tle 后来在jesful大神指导下，对极角排序的单调性质重新理解了下。才ac的
此题用补集的性质，将钝角的部分算出来，然后用c（n，3）去剪就可以了。
首先将以i点为源点的极角算出来，然后排序，确定第二个点J 在1——（n-1）那么下面的做法就有不同了。
我们很容易想到枚举K点使得I J K构成的三角形是钝角。那么这样做法是o（n^3）我就是这样超时的。即使你k点的枚举是j+1开始的也会超时。
而且这地方还有就是要考虑明确当相减的时候会存在&pi的情况，那么这时候你要统计2pi-当前值的才是三角形的内角。
现在说下卡了我一下午的代码其实只有两行。
单调队列的优化是基于以下的思想：
够成钝角的点都是在平面的一个区间内的，并且这个区间，是随着J点极角的增大，单调向顺时针移动的。那么，既然有这个单调性，
我们就可以用类似单调队列的方法，随着J点的推移，那个要查找的区间端点也可以单调推移，光维护这端点，那么指针不回退，每个点扫描一次，达到了O（N），每个操作均摊O（1）
但是此题要维护的队列其实有两个即pi/2 和pi的区间。由于我一直在想怎么维护大于pi的那段区间去了，一直想不到。其实是不必要的。因为我们在维护同时在后继已经扫到了。
所以我只需要用pi的区间个数减去pi/2的区间个数就可以了。
对于此题如果大神觉得有误请指正！因为我看到网上有只用pi/2维护的个数 然后-c（n，3）*2 我一直不知道此方法是怎么做到ac的如果大神知道请指教！！！
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：163887次
积分：4453
积分：4453
排名：第2968名
原创：282篇
转载：31篇
评论：53条
(2)(1)(2)(10)(4)(1)(24)(59)(26)(54)(6)(10)(36)(65)(12)(1)Remember the Word(前缀树&树上DP) - 推酷
Remember the Word(前缀树&树上DP)
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &
3942 - Remember the Word
Neal is very curious about combinatorial problems, and now here comes a problem about words. Knowing that Ray has a photographic memory and this may not trouble him, Neal gives it to Jiejie.
Since Jiejie can't remember numbers clearly, he just uses sticks to help himself. Allowing for Jiejie's only
sticks, he can only record the remainders of the numbers divided by total amount of sticks.
The problem is as follows: a word needs to be divided into small pieces in such a way that each piece is from some given set of words. Given a word and the set of words, Jiejie should calculate the number of ways the given word can be divided, using the words in the set.
The input file contains multiple test cases. For each test case: the first line contains the given word whose length is no more than 300 000.
The second line contains an integer
Each of the following
lines contains one word from the set. Each word will be at most 100 characters long. There will be no two identical words and all letters in the words will be lowercase.
There is a blank line between consecutive test cases.
You should proceed to the end of file.
For each test case, output the number, as described above, from the task description modulo .
该题为大白(刘汝佳。入门经典训练指南)上一道例题。p209。
dp[i]=sum(dp[i+len(x)])
dp[i]表示从字符i开始的字符串即后缀(s[i..L])的分解方案数。
(s[i..L]的前缀。
详细见代码：
#include &iostream&
#include&string.h&
#include&stdio.h&
const int md=400110;//单词数乘上单词长度。顶多一个单词一条路径
const int ssz=26;
const int maxn=300010;
const int mod=;
char words[maxn];
int dp[maxn];
struct Trie
int ch[md][ssz];
int val[md];
void init()
memset(ch[0],0,sizeof ch[0]);
int idx(char c)
return c-'a';
void inser(char *s)
int u=0,n=strlen(s);
for(int i=0; i&n; i++)
int c=idx(s[i]);
if(!ch[u][c])
memset(ch[sz],0,sizeof ch[sz]);
val[sz]=0;
ch[u][c]=sz++;
u=ch[u][c];
val[u]=n;//可以传参数初始化
void sear(char *s,int p,int len)
for(int i=0; i& i++)//字符一个一个查找
int c=idx(s[i]);
if(!ch[u][c])//前缀搜完
u=ch[u][c];
if(val[u])
dp[p]=(dp[p]+dp[p+val[u]])%
int main()
int i,s,len,cas=1;
char tmp[110];
while(~scanf(&%s&,words))
scanf(&%d&,&s);
len=strlen(words);
tree.init();//开始忘了初始化。调了半天。。。。。
dp[len]=1;//注意这个位置的初始化！
for(i=0; i&s; i++)
scanf(&%s&,tmp);
tree.inser(tmp);
for(i=len-1; i&=0; i--)
tree.sear(words+i,i,len-i);
printf(&Case %d: %d\n&,cas++,dp[0]);
已发表评论数()
&&登&&&陆&&
已收藏到推刊！
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见2691人阅读
本文出自 &&
刘汝佳《算法竞赛入门经典-训练指南》的动态规划部分的习题Beginner &
这个专题一共有25题，刷完后对dp的感觉提升了不少。
现把解题报告整理了一下，希望对大家能有帮助。
入门习题 （Exercises: Beginner）
Partitioning by Palindromes
Wavio Sequence
可以转化为经典问题，时间O(nlogn)
Fewest Flops
序列划分模型；状态设计
Palindromic Subsequence
可以转化为LCS
Cellular Network
需要一点概率知识和推理
Mega Man's Missions
基础的集合动态规划
Joseph问题的变形
Martian Mining
模型简单，但需要减少重复计算
Paths through the Hourglass
类似01 背包问题
Headmaster's Headache
集合动态规划
Strategic Game
树上动态规划（基础题）
String Compression
字符串动态规划
Dance Dance Revolution
以跳舞机为背景的题目
Twenty Questions
有趣的问题；比较基础的动态规划
Storage Keepers
Make Palindrome
*(extra)UVa10254
The Priest Mathematician
**(extra)UVa437
The Tower of Babylon
**(extra)UVa442
Matrix Chain Multiplication
最优矩阵乘法
**(extra)UVa473
Raucous Rockers
**(extra)UVa590
Always on the Run
**(extra)UVa607
Scheduling Lectures
**(extra)UVa662
**(extra)UVa672
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：488696次
积分：9697
积分：9697
排名：第718名
原创：422篇
评论：245条
文章：15篇
阅读：21942
文章：17篇
阅读：37153
文章：61篇
阅读：70228
(3)(37)(80)(8)(5)(30)(6)(21)(1)(7)(28)(47)(36)(38)(63)(4)(9)(2)(10)此题居然备注是请读者自己思考。。。。。。我是不是太菜了呢？ 我是没有思考出来
我本来想如果我把每次拿出i本书的所有状态都存下来。然后在依次往上找是不是算构造来最优子结构？但是此方法太暴力。而且我也不知到该怎么存下来。
虽然我开始确实想到来用状态压缩。但是我不知到怎么保存各个状态后我拿掉某个对于另外一个的个数加减造成的影响。比方说 25 25 26 26 25 25 那么如果状态表示那么拿的状态是 但是如果我左边25放一个到右边25那么状态是没变化的。可能是我没想到把。。。后来呢我还是选择来搜题解。。。想不到现场赛题目这么难啊这么难四维的状态然后还加上状态压缩和滚动数组。。。弱爆了我。
以下题节我参照了几个博客的：
http://blog.csdn.net/woshi250hua/article/details/7743328
http://blog.csdn.net/acm_ted/article/details/7835602
/huicpc0328/item/20d4cffc9c778ac8
说下正文：
首先：这个大家都想到把，由于书的高度介于25和32之间，可以把书的高度减去25变成介于0和7之间，这个数字就很适合状态压缩了。
然后：思考的时候就尽量往高度进行压缩。每本书有两种选择，一种留下，一种抽走，留下的书和抽走的书可以用两个状态表示，如果抽出去的书不在留下的书里面，那么最后就要增加一段。每本书似乎只和留下来的最后一本书的状态有关，如果书的高度和留下的最后一本书的高度相同，那么可以直接合并进去而不必计算高度，如果不相同则要增加段数
这里我觉得为什么要和最后一本书有关呢？ 其实在状态后设置一维存状态高度，那么相对与每个状态的各个高度放最后我门都有遍历到。因为我从最开始什么书都没有然后每次往里放一本或抽一本，当放一本进去的时候比较的是当前书架上已经存在的书，所以如果不存在那么其实就只要和最后一本有关啦（个人见解，如有错误还望指正，感激不尽）
接下来：那我们要怎么表示抽走的状态呢？压缩成一个数字吗？不行，还必须和k扯上关系，也就是说必须有一维表示数量，而抽走书的种类可以用总状态减去留下来的状态来表示。这样就可以用dp[i][j][k][s]来进行状态转移，dp[i][j][k][s]表示到第i本书时取走j本书留下来的书状态为k最后一本书高度为s。状态转移见代码。复杂度O（n*k*(1&&8)*8)。
这里我还有最后一个地方不懂，就是为什么最后要统计没有输入的书的状态个数呢？？即我最后一行我代码统计min的时候要抑或的地方，我觉得为什么不直接是begin呢？但是我试着交代码错了。！！求教大神提点！
#include &iostream&
#include &cstdio&
#include&cstring&
#include&algorithm&
const int INF= 0x3f3f3f3f;
int tall[105],num[1&&8];
int dp[2][110][1&&8][10];
void init()
memset(num,0,sizeof(num));
//求每个状态中书的数目
for(int i=0;i&(1&&8);++i)
for(int j=0;j&8;++j)
if(i&(1&&j))num[i]++;
void preinit(int K,int cur)
for(int j=0;j&=K;++j)
for(int k=0;k&(1&&8);++k)
for(int s=0;s&=8;++s)
dp[cur][j][k][s]=INF;
int main()
int n,m,begin,cas=1;
while(scanf(&%d%d&,&n,&m)!=EOF)
if(n==0)return 0;
//初始高度状态
for(int i=1;i&=n;++i)
scanf(&%d&,&tall[i]);
tall[i]-=25;
//统计高度个数
begin |=(1&&tall[i]);
for(int i=0;i&=m;++i)//取走的次数
for(int j=0;j&(1&&8);++j)//高度状态
for(int k=0;k&=8;++k)//最后的书的高度
dp[0][i][j][k]=INF;
dp[0][0][0][8]=0;//起始点
for(int i=1;i&=n;++i)
int cur=1&i;
int pre=1-
preinit(m,cur);
for(int j=0;j&i&&j&=m;++j)
for(int k=0;k&(1&&8);++k)
for(int s=0;s&=8;++s)//因为此题我对于每个状态都设置了一维来存各个状态下的最后一个数，所以所有情况都可以遍历到
if(dp[pre][j][k][s]!=INF)
int curstk=k|(1&&tall[i]);//当前状态（放入i高度的书）
//取走第i位,且还可以取走
//如果还可以取书或者放书，那么我就要比较对于当前状态和前一个状态哪个下，如果在放一本书后哪个的情况更小
dp[cur][j+1][k][s]=min(dp[cur][j+1][k][s],dp[pre][j][k][s]);
//取走第 i 位的书且高度与前一个相同（在留下的书里面）
if(s==tall[i])
dp[cur][j][k][s]=min(dp[cur][j][k][s],dp[pre][j][k][s]);
//不取走第 i 位且高度与前一个不同
dp[cur][j][curstk][tall[i]]=min(dp[cur][j][curstk][tall[i]],dp[pre][j][k][s]+1);
int ans=INF;
int cur=n&1;
for(int i=0;i&=m;++i)
for(int j=0;j&(1&&8);++j)
for(int k=0;k&8;++k)
if(dp[n&1][i][j][k]!=INF)
int temp=j^//不在初始状态且拿出的书(高度)
ans=min(ans,dp[cur][i][j][k]+num[temp]);
//ans=min(ans,dp[cur][i][begin][k]);
printf(&Case %d: %d\n\n&,cas++,ans);
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：163890次
积分：4453
积分：4453
排名：第2968名
原创：282篇
转载：31篇
评论：53条
(2)(1)(2)(10)(4)(1)(24)(59)(26)(54)(6)(10)(36)(65)(12)(1)