The Fourth Dimension Space

POJ 2348 Euclid's Game 博弈问题

首先结果不可能有二义性，即必须是某个确定的人获胜(W)。

如果谁先获得选择权那么他就能决定在子结构中是先手还是后手。有的时候要选择先手，有时后手，谁先具有选择权，谁就能得到他想要的顺序(O).

如果没有一个人能获得选择权，比如说大数始终不是小数的2倍或以上，那么只能看天意了(F).

so the function is:
wisdom + option + fortune = success

PS:做完之后的确觉得简单，但是要能想到它却不容易。关于博弈问题，目前还处在做一题会一题的状态，希望再做几题能触类旁通吧。

posted @ 2010-03-08 16:40 abilitytao 阅读(432) | 评论 (0) | 编辑收藏

POJ 1463 Strategic game 第二个树形DP

做第二的时候一看就知道是个树形DP了原来树形DP的模式这么固定。。。但是那个递推方程确实还不能一下子想到，可能还需要积累些经验。

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

vector<int>hash[1500];

int n;

int s[1500];

int dp[1500][2];

int root;

void dfs(int x)

{

int i,j;

int len=hash[x].size();

for(i=0;i<len;i++)

dfs(hash[x][i]);

if(len==0){dp[x][0]=0;dp[x][1]=1;}

else

{

for(i=0;i<len;i++)

{

dp[x][0]+=dp[hash[x][i]][1];

dp[x][1]+=min(dp[hash[x][i]][0],dp[hash[x][i]][1]);

}

dp[x][1]++;

}

int main()

{

int v,t,num;

int i,j;

while(scanf("%d",&n)!=EOF)

{

memset(dp,0,sizeof(dp));

memset(s,0,sizeof(s));

for(i=0;i<n;i++)

hash[i].clear();

for(i=1;i<=n;i++)

{

scanf("%d:(%d)",&v,&num);

for(j=1;j<=num;j++)

{

scanf("%d",&t);

hash[v].push_back(t);

s[t]=1;

}

for(i=0;i<n;i++)

if(s[i]==0){root=i;break;}

dfs(root);

printf("%d\n",min(dp[root][0],dp[root][1]));

}

return 0;

}

posted @ 2010-03-08 00:38 abilitytao 阅读(1597) | 评论 (0) | 编辑收藏

POJ 1947 Rebuilding Roads 第一个树形DP

After solving this problem,I can't help admitting that DP is a world which fully fill with amazement，from the simple one dimension DP,to two dimension DP even to staue DP,tree DP,DP problem is just like a kaleidoscope. But the further reflection reveal that it is always the same because of the similar essence.in my eyes,every DP problem has a (mostly two dimension)table and a equation bewteen two states.If we can controll the table and the relationship between every states,we can conque the problem completely.
The following is my code ,according to the big fish foreverlin.

#include<iostream>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define INF 999999999

#define MAX 151

vector<int> hash[MAX];

int dp[MAX][MAX];

int n,p;

void dfs(int x)//x代表当前访问结点

{

int i,j,k;

int len=hash[x].size();

for(i=0;i<len;i++)

dfs(hash[x][i]);

//////////////////////////////////////////////////////////////////////////

//后序遍历，从叶子往上逐层递推

if(x==1) dp[x][1]=hash[x].size();

else dp[x][1]=hash[x].size()+1;

for(k=0;k<len;k++)

{

for(i=p-1;i>=1;i--)

{

if(dp[x][i]!=INF)

{

for(j=1;i+j<=p;j++)

{

if(dp[hash[x][k]][j]!=INF)

dp[x][i+j]=min(dp[x][i+j],dp[x][i]+dp[hash[x][k]][j]-2);

}

int main()

{

scanf("%d%d",&n,&p);

int i,j;

int t1,t2;

for(i=1;i<=n-1;i++)

{

scanf("%d%d",&t1,&t2);

hash[t1].push_back(t2);

}

for(i=1;i<=n;i++)

for(j=1;j<=p;j++)

dp[i][j]=INF;

dfs(1);

int ans=INF;

for(i=1;i<=n;i++)

{

if(dp[i][p]<ans)

ans=dp[i][p];

}

printf("%d\n",ans);

return 0;

}

posted @ 2010-03-07 23:36 abilitytao 阅读(1170) | 评论 (0) | 编辑收藏

再品苏轼

却对酒杯疑是梦，
试拈诗笔已如神。
此灾何必深追咎，
窃禄从来岂有因。

和子由渑池怀旧赏析
苏轼
人生到处知何似？应似飞鸿踏雪泥。
泥上偶然留爪印，鸿毛那复计东西。
老僧已死成新塔，坏壁无由见旧题。
往日崎岖君记否；路长人困蹇驴嘶。

蝶恋花
年代：宋作者：苏轼

花褪残红青杏小。燕子飞时，绿水人家绕。枝上柳绵吹又少，天涯何处无芳草？
墙里秋千墙外道。墙外行人，墙里佳人笑。笑渐不闻声渐悄，多情却被无情恼。

雪后书北台壁二首
年代：宋作者：苏轼

黄昏犹作雨纤纤，夜静无风势转严。
但觉衾裯如泼水，不知庭院已堆盐。
五更晓色来书幌，半夜寒声落画檐。
试扫北台看马耳，未随埋没有双尖。
城头初日始翻鸦，陌上晴泥已没车。
冻合玉楼寒起粟，光摇银海眼生花。
遗蝗入地应千尺，宿麦连云有几家。
老病自嗟诗力退，空吟冰柱忆刘叉。

史记：刘叉《冰柱》诗歌鉴赏翻译原文

刘叉

　　师干久不息，农为兵兮民重嗟。

　　骚然县宇，土崩水溃，畹中无熟谷，垅上无桑麻。

　　王春判序，百卉茁甲含葩。

　　有客避兵奔游僻，跋履险阨至三巴。

　　貂裘蒙茸已敝缕，鬓发蓬舥。

　　雀惊鼠伏，宁遑安处，独卧旅舍无好梦，更堪走风沙！

　　天人一夜剪瑛琭，诘旦都成六出花。

　　南亩未盈尺，纤片乱舞空纷拏。

　　旋落旋逐朝暾化，檐间冰柱若削出交加。

　　或低或昂，小大莹洁，随势无等差。

　　始疑玉龙下界来人世，齐向茅檐布爪牙。

　　又疑汉高帝，西方来斩蛇。

　　人不识，谁为当风杖莫邪。

　　铿锵冰有韵，的玉无暇。

　　不为四时雨，徒于道路成泥柤。

　　不为九江浪，徒为汩没天之涯。

　　不为双井水，满瓯泛泛烹春茶。

　　不为中山浆，清新馥鼻盈百车。

　　不为池与沼，养鱼种芰成霪霪；

　　不为醴泉与甘露，使名异瑞世俗夸。

　　特禀朝沏气，洁然自许靡间其迩遐。

　　森然气结一千里，滴沥声沉十万家。

　　明也虽小，暗之大不可遮。

　　勿被曲瓦，直下不能抑群邪。

　　奈何时逼，不得时在我梦中，倏然漂去无余。

　　自是成毁任天理，天于此物岂宜有忒赊。

　　反令井蛙壁虫变容易，背人缩首竞呀呀。

　　我愿天子回造化，藏之韫椟玩之生光华。　　

　　从唐德宗贞元末到宪宗元和时期，以韩愈为首的一派诗人，一反大历以来圆熟浮丽的诗风，走上险怪幽僻一路。如韩愈的《陆浑山火》和卢仝的《月蚀诗》等都足以代表这种诗风。刘叉也是这一诗派的著名人物，以《冰柱》、《雪车》二诗为最有名，而《冰柱》诗尤奇谲奔放，寄托遥深，为后世所称扬。

　　全诗可分为三段。

　　从首句到“更堪走风沙”为第一段。在这一段里，诗人首先揭露了当时的社会现实：干戈不息，民不聊生。安史乱后，接着出现藩镇割据的局面，而吐蕃也多次出兵骚扰西南边疆，诗里所说的“骚然县宇，土崩水溃，畹中无熟谷，垅上无桑麻”，反映了当时因战祸连绵而造成的田园荒芜景象。诗人为了躲避兵灾，逃向四川，而四川也非乐土。旅途是艰辛的，漫长的，而在兵荒马乱中跋山涉川，不仅要忍受风霜劳顿之苦，还要时时提防恶人的侵害。“貂裘蒙茸已敝缕，鬓发蓬舥，雀惊鼠伏”，写出了旅途中的狼狈情景，为下文借写冰柱抒发感喟作了铺垫。

　　从“天人一夜剪瑛琭”到“直下不能抑群邪”为第二段。这一段是全诗的主要部分，描绘了冰柱的奇丽景色。在一夜大雪之后，房檐间的冰柱垂挂下来，大大小小，高高低低，一样的晶莹洁白，玉色琼辉。它不是冰柱，而是天上玉龙的爪牙；它不是冰柱，而是汉高帝的斩蛇宝剑！这两个奇特的比喻，不仅写出了冰柱的风神，还为下文写它的不为世用张势：它不能化为及时雨，使田禾滋壮；而只能化为泥浆，使道路艰难。它不能化为九江的波浪，奔向大海；而只能浸没于峡谷，沉沦于天涯。它不能化为双井名泉，煮茗煎茶；它不能化为中山美酝，芳香四溢。它不能蓄而为池，积而为沼，养鱼种芰；它不能为甘泉，不能为饴露，使这特异的祥瑞征兆为世俗赞夸。它只能凭着它的清沏之气，孤洁自赏，自凝自消。它的光彩虽不大，却无法掩遮；它负着曲瓦，不能施展神锋，铲除奸邪。这一大段的描绘，句句是在写冰柱，却句句关合到诗人自己。诗人的怀才不遇的激愤之情，刚傲不羁的性格，全面地显示了出来。

　　从“奈何时逼”到末句为第三段。这一段写冰柱消失以后的感慨。天晴冻解，冰柱从梦中消失，杳无踪迹。万物的成与毁是天决定的，它对于冰柱不会特加恩泽，却反而使那些井蛙壁虫，顺生易长，背着人，缩着头，聒噪不休。希望天子能回造化之力，把冰柱珍藏在柜子里，使它永远放出光辉。这一段比上一段更深一层，拿容易消失的冰柱和最易繁衍的蛙虫对比，揭示出当时政治上的小人横行、贤士在野的情况。最后诗人把理想寄托在皇帝身上，希望他能挽转形势，重用贤才。诗的最后两句是画龙点晴，点出了诗的主题，就是说只要皇帝能重用贤士，排斥奸邪，就能消弭战祸，天下太平。

　　这首诗在艺术上很有特色，以冰柱入诗，题材新奇。更奇的是对冰柱的形象描写，把冰柱拟人化，句句是写冰柱，也是句句在表露自己的怀才不遇。他用玉龙的爪牙，刘邦的斩蛇宝剑来比喻冰柱，贴切而新鲜，为修辞手法创一特例。就诗体来说，这首诗是句子长短不一的杂言体，抒写较自由，适宜于表现较复杂的思想感情。用这种诗体，不可避免的是多议论，散文化。刘叉的这首诗显然是受《月蚀诗》的影响，而又加以发展，显得更为奇谲奔放。使这首诗显出它的最大特色的是在用韵方面。它用的是麻韵，麻韵字的音是响亮的，高亢的，但韵字却比较少，因有“险韵”之称。这首诗共二十七韵，全属麻韵，中间的“舥”字，“柤”字很少有人用过。“邪”字用了两次，前一个音“牙”，是剑名；后一个音“霞”，是奸邪之“邪”的另一读，音义不同，故得同用。用麻韵写古体诗，一韵到底的很罕见。本诗在抒写中一气贯下，纵横自如，在描绘冰柱一段，连用了六个“不为”排句，气势浩荡，郁结于胸中的不平之气，喷薄而出，“特禀朝沏气，洁然自许靡间其迩遐”两句，拗折多姿；“森然气结一千里，滴沥声沉十万家”两句，对仗整饬。这些句式的变化是和感情的起伏跌宕密切相连的，句子或长或短，或对仗，或散行，而最后都能很自然地落到韵脚上来，毫无生拼硬凑的毛病，用险韵而不觉其险，显示出诗人的才华，为唐代诗坛增添了光彩。宋代苏轼在《雪后书北台壁二首》中用“尖”“叉”二韵，第二首的末两句是：“老病自嗟诗力退，寒吟《冰柱》忆刘叉。”可以看出他对于刘叉的《冰柱》诗是很赞赏的。　　（李廷先）

posted @ 2010-03-06 23:02 abilitytao 阅读(301) | 评论 (1) | 编辑收藏

航电3月月赛

最后一题 1010 传递闭包

#include<iostream>

using namespace std;

int mm[200][200];

int main()

{

int n,m;

while(scanf("%d%d",&n,&m))

{

memset(mm,0,sizeof(mm));

int flag=0;

if(n==0)

break;

int i,j;

for(i=1;i<=m;i++)

{

int t1,t2;

scanf("%d%d",&t1,&t2);

mm[t1][t2]=1;

}

int k;

for(k=0;k<n;k++)

{

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

if(mm[i][k]==1&&mm[k][j]==1)

mm[i][j]=1;

}

for(i=0;i<n;i++)

{

for(j=i+1;j<n;j++)

{

if(mm[i][j]==1&&mm[j][i]==1)

{

flag=1;

break;

}

if(flag)

break;

}

if(flag)

printf("NO\n");

else

printf("YES\n");

}

return 0;

}

1004 KMP算法

#include<iostream>

using namespace std;

char str[200010];

int next[200010];

int dp[200010];

inline void calnext(char s[],int next[])

{

int i;

int j;

int len=strlen(s);

next[0]=-1;

j=-1;

for(i=1;i<len;i++)

{

while(j>=0&&s[i]!=s[j+1])

j=next[j];

if(s[j+1]==s[i])//上一个循环可能因为j=-1而不做，此时不能知道s[i]与s[j+1]的关系。故此需要此条件。

j++;

next[i]=j;

}

int main()

{

int n;

int t;

scanf("%d",&t);

int i,j;

int sum;

for(i=1;i<=t;i++)

{

scanf("%d",&n);

scanf("%s",str);

calnext(str,next);

dp[0]=1;

sum=1;

for(j=1;j<n;j++)

{

if(next[j]==-1)

{

dp[j]=1;

sum++;

sum%=10007;

}

else

{

dp[j]=dp[next[j]]+1;

sum+=dp[j];

sum%=10007;

}

printf("%d\n",sum);

}

return 0;

}

posted @ 2010-03-06 17:15 abilitytao 阅读(1197) | 评论 (0) | 编辑收藏

POJ 2836 Rectangular Covering

这题确实搞人，从北京一直想回南京，终于在今天看完一个高人的代码之后弄明白了。其实这题只要经过一个3次方的预处理后，剩下的就是一背包问题。背包的重量是点集所代表的状态，背包的价值是矩形的面积和。做完这题，算是基本上知道状态DP是什么情况了，就是用一个bitset记录下用过与否，其实根本就没什么长进。

posted @ 2010-03-06 00:01 abilitytao 阅读(1160) | 评论 (0) | 编辑收藏

Topcoder 463 Div 2 1000

Problem Statement

Taro and Hanako are playing a game called Nisoku, which is played as follows. Initially, there is a pile of cards. Each card contains a real number between 1.5 and 10.0, inclusive. You are given a vector <double> cards, the i-th element of which is the number written on the i-th card.

Repeat the following step until there is only one card left in the pile: Remove any two cards from the pile, and add one new card to the pile. Write either a+b or a*b on the new card, where a and b are the numbers written on the two cards that were removed.

Return the maximal possible number written on the final card in the pile.

Definition

Class:	Nisoku
Method:	theMax
Parameters:	vector <double>
Returns:	double
Method signature:	double theMax(vector <double> cards)
(be sure your method is public)

Notes

-

Your return value must have an absolute or relative error less than 1e-9.

Constraints

-

cards will contain between 2 and 50 elements, inclusive.

-

Each element of cards will be between 1.5 and 10.0, inclusive.

Examples

0)

{5, 8}

Returns: 40.0

5 * 8 = 40.

1)

{1.5, 1.8}

Returns: 3.3

1.5 + 1.8 = 3.3.

2)

{8.26, 7.54, 3.2567}

Returns: 202.82857868

3)

{1.5, 1.7, 1.6, 1.5}

Returns: 9.920000000000002

4)

{10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10}

Returns: 1.0E50

The answer can be extremely big.

发现偶还是太水了。。。

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

class Nisoku

{

public:

double theMax(vector<double>cards)

{

int i,j;

sort(cards.begin(),cards.end());

double ans=0;

for(i=0;i<=cards.size();i+=2)

{

double p=1;

for(j=0;j<i/2;j++)

p*=(cards[j]+cards[i-1-j]);

for(j=i;j<cards.size();j++)

p*=cards[j];

ans=max(ans,p);

}

return ans;

}

};

谁能证明下这份代码的正确性？

posted @ 2010-03-02 22:27 abilitytao 阅读(1043) | 评论 (0) | 编辑收藏

动态规划——思想者的游戏

dynamic programming.

posted @ 2010-02-23 21:21 abilitytao 阅读(254) | 评论 (0) | 编辑收藏

北京之行

1.各火车站到新东方总部的乘车路线

北京站—总部（新东方大厦）：乘地铁2号线到西直门下车，步行至西直门外换乘808、运通105、运通106、运通205等到海淀黄庄北下车。下车后经过街天桥到路西侧，沿中关村广场步行街走到头即是新东方总部。
北京西站—总部（新东方大厦）：
乘320、特6路到海淀黄庄北下车。下车后经过街天桥到路西侧，沿中关村广场步行街走到头即是新东方总部。

北京南站—总部（新东方大厦）：
乘特5路到甘家口北下车，换乘320、特6路到海淀黄庄北下车。下车后经过街天桥到路西侧，沿中关村广场步行街走到头即是新东方总部。
北京北站—总部（新东方大厦）：
步行至西直门外，乘运通205、运通106、运通105、808等到海淀黄庄北下车。下车后经过街天桥到路西侧，沿中关村广场步行街走到头即是新东方总部。机场—总部（新东方大厦）：乘机场地铁线到三元桥下车换乘地铁10号线到海淀黄庄下车。A2出口出,出来后马路对面沿步行街直走,走到头.家乐福超市西侧，鼎好电子城西南侧。咨询电话：010-82611818转0。

2.新东方总部
新东方大厦（总部）（周一至周日8：00-18：30）：海淀中街6号金融中心B座 3层，可乘坐特6、特4、307、355、726、365、 801、302、826、731、814、320等到中关村或海淀黄庄下车；地铁4号线到中关村站从D口出来。地铁10号线到海淀黄庄站下A2出口出,出来后马路对面沿步行街直走,走到头即是.位于家乐福超市西侧，鼎好电子城西南侧。咨询电话：010-82611818转0。

3.北京永正商务酒店　电话：010-62565550

4.万通驿站　苏州街店　电话:010 52719998

5.图书城

　　地址：海淀区西大街39号

　　乘车路线：运通118、26、394、运通119、944支、运通110、运通114 北京地震局下车。运通113、740 外环、751、913、982、983 支海淀桥西下车，往回走过海淀桥路东见昊海楼。732、808、332、333 内环、394、运通106、运通114、718，海淀桥北下车。913、641、944 支、982、983 支、718、808、运通110、运通113、运通109，中关村西站下车。

posted @ 2010-02-14 21:56 abilitytao 阅读(298) | 评论 (0) | 编辑收藏

除夕之夜的动态规划　POJ 1015 Jury Compromise

摘要: 写了３个小时终于过了，这道题让我进一步了解和掌握了动态规划，呵呵:-) #include<iostream>#include<cstdio>#include<algorithm>using namespace std;#define offset ((20*m))int f[100][2000];int&nbs... 阅读全文

posted @ 2010-02-13 19:03 abilitytao 阅读(1948) | 评论 (0) | 编辑收藏

The Fourth Dimension Space

导航

统计

常用链接

留言簿(16)

随笔档案

文章档案

Blogs in Computer Vision and Algorithm

友情链接

搜索

最新评论

阅读排行榜

评论排行榜

POJ 2348 Euclid's Game 博弈问题

POJ 1463 Strategic game 第二个树形DP

POJ 1947 Rebuilding Roads 第一个树形DP

再品苏轼

航电3月月赛

POJ 2836 Rectangular Covering

Topcoder 463 Div 2 1000

Problem Statement

Definition

Notes

Constraints

Examples

动态规划——思想者的游戏

北京之行

除夕之夜的动态规划　POJ 1015 Jury Compromise