简易DP——最长上升子序列 poj 2533

//状态为数组第位置k，作为每个子序列的末位，状态值为最长上升子序列长度，初始L[0]=1

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<string>

int k,n,ct,arr[1010],L[1010];

int main()

{

int i,j,max;

scanf("%d",&n);

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

scanf("%d",&arr[i]);

L[0]=1;

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

{

max=0;

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

if(arr[j]<arr[i]&&L[j]>max)max=L[j];

L[i]=max+1;

}

max=0;

for(i=0;i<n;++i)//此循环不可少，因为L[n-1]为包含最后一个数字的最大串长度，题目未加此条件

if(max<L[i])max=L[i];

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

return 0;

}

posted @ 2011-08-04 19:35 拥梦的小鱼阅读(496) | 评论 (0) | 编辑收藏

递归深搜——poj 1321,类八皇后

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<string>

int k,n,ct,num_p,col[10],ans[92][10],row[10];//col记录第i行放棋子所在的列号

char bd[10][10];//棋盘布局

void queen(int i)

{

int j,t;

if(num_p==k)//不同于八皇后，k不一定为8，有题目给出

{

/*for(j=0;j<n;++j)记录可能方案情况，此题不要求

ans[ct][j]=col[j]+1;*/

ct++;

return ;

}

if(i==n)return ;//少了此条件则n无限大

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

{

if(bd[i][j]=='.')continue;

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

if(col[t]==j)break;

if(t==i)

{

col[i]=j;

num_p++;

queen(i+1);

num_p--;

col[i]=9;

}

if(k<n)//不同于八皇后，第i行可以不放棋子，故深搜多一条支路

{

//num_p++;

queen(i+1);

//num_p--;

}

int main()

{

int i,j;

while(scanf("%d%d",&n,&k)==2&&n!=-1&&k!=-1)

{

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

{

scanf("%s",bd[i]);

}

queen(0);

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

ct=0;

memset(col,0,sizeof(col));

memset(row,0,sizeof(row));

}

return 0;

}

posted @ 2011-08-04 19:08 拥梦的小鱼阅读(732) | 评论 (0) | 编辑收藏

POJ题目分类

摘要: 多版本的POJ分类流传最广的一种分类：初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. &n... 阅读全文

posted @ 2011-08-02 11:03 拥梦的小鱼阅读(3680) | 评论 (0) | 编辑收藏

背包系列 POJ——1276 多重背包

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cmath>

int inline MAX(int a,int b)

{

if(a>b) return a;

else return b;

}

int N[15],D[15],dp[100010];

int main()

{

int n,i,j,k,amt,cash;

while(scanf("%d%d",&cash,&n)==2)

{

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

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

{

scanf("%d%d",&N[i],&D[i]);

dp[D[i]]=D[i];

}

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

{

if(D[ i ]*N[ i ]>=cash)//该物品最多超过了总容量，完全背包

{

for( j = D[i]; j<=cash ; ++j)//j由小变大，因为每件物品个数有无限个，可重复放入！！<=中=不可少，否则WA

dp[j]=MAX(dp[j],dp[ j - D[i] ]+D[i]);

}

else//多重背包

{

k=1;

amt=N[i] ;

while( k < amt )

{

for( j = cash ; j >=k* D[i] ; --j)//j由大变小，因为后面的先改变后不会影响前面的，反之则不行！！

dp[j]=MAX(dp[j],dp[ j - D[i]*k ]+D[i]*k);

amt-=k;

k*=2;

}

for( j = cash ; j >=amt* D[i] ; --j)

dp[j]=MAX(dp[j],dp[ j - amt*D[ i ] ]+amt*D[ i ]);//头开始理解偏差，正确理解：amt现为分解为2^k后剩下的散量，

//即可供使用的物品数

}

printf("%d\n",dp[cash]);

}

return 0;

}

posted @ 2011-08-02 11:00 拥梦的小鱼阅读(396) | 评论 (0) | 编辑收藏

不知道做什么时的任务

楼天成男人八题：http://wenku.baidu.com/view/468be87ca26925c52cc5bf30.html

多重背包使用单调队列：http://jiyuede.blog.163.com/blog/static/33251921201092423943387/

dp解题报告总结：http://blog.sina.com.cn/s/blog_79b832820100rlis.html

男人八题上：http://hi.baidu.com/wywy/blog/item/862d8fd48003ba19a18bb7f2.html

男人八题下：http://hi.baidu.com/wywy/blog/item/2f5fa58bb32718679f2fb40c.html

NOIP常用的DP：http://www.cppblog.com/hurrican6/archive/2010/08/08/122665.html

二分图的问题：http://www.cnblogs.com/DreamUp/archive/2010/08/18/1802039.html

状态压缩DP：http://blog.csdn.net/accry/article/details/6607703

LCA问题的一些总结：http://jiyuede.blog.163.com/blog/static/332519212010619112023502/

LCA和RMQ：http://www.cppblog.com/superKiki/archive/2010/05/08/114838.html

RMQ和LCA：http://dongxicheng.org/structure/lca-rmq/

动态规划：http://www.cppblog.com/linyangfei/archive/2008/04/20/32674.html

动态规划专题总结（好东西）：http://zebozhuang.blog.163.com/blog/static/1714798042011324738651/

按位DP小结：http://hi.baidu.com/soy_sevenzero/blog/item/51143533c9ec4408eac4afc2.html

POJDP题：http://apps.hi.baidu.com/share/detail/11049126

算法与信息学竞赛中的题目POJ：

posted @ 2011-08-02 10:03 拥梦的小鱼阅读(201) | 评论 (0) | 编辑收藏

题意：
就是说一个天平，给了C个距离（坐标），G个砝码，问砝码全用上，有几种让它平衡的办法。
dp[i][j]表示在挂上前i个物体的时,平衡度为j(j>0时表示左边重,j=0时表示天平平衡,j<0时表示右边重)时挂法的数量,而根据题意可以确定j的取值范围为:[-7500,7500],于是可以得到状态转移方程为:
dp[i][j]+=(dp[i-1][j-p[k]*g[i]]), p[k]表示第k个挂钩的位置,g[i]为第i个砝码的重量
由于j-p[k]*g[i]可能为负数,因此统一加上7500,那么初始状态dp[0][7500]=1(此时表示天平平衡),表示不用物体且使得天平平衡时的方法只有一种.

// (1)用二维数组的 01背包解。一个一个砝码往上放，头开始 is[0][7500]=1，指0个砝码时为平衡7500，此时有一种方法。

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<string>

int wi[26],dis[26],is[26][15005],C,G;//力矩的极值为-7500，7500.下标为正，故计算时+7500

void ZeroOnepack()

{

int i=0,j,k;

//for(i=1;i<=G;i++)

// {

// for(j=-7500;j<=7500;j++)

// for(k=1;k<=C;k++)

// //if(j+7500>=dis[k]*wi[i])

// is[i][j+7500]+=is[i-1][j+7500-dis[k]*wi[i]];

// }

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

{

for(j=-7500;j<=7500;j++)

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

//if(j+7500>=dis[k]*wi[i])

is[i][j+7500]+=is[i-1][j+7500-dis[k]*wi[i-1]];//考虑放第i个砝码时的情况数，在第i-1个砝码上加。

}

int main()

{

int i=0,tem=0,yz,neg,ws=0,a=1,b=1;

scanf("%d%d",&C,&G);

//for(i=1;i<=C;++i)

//{

// scanf("%d",&dis[i]);

//}

//for(i = 1 ; i <= G ; ++i )

//{

// scanf("%d",&wi[i]);

//}

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

{

scanf("%d",&dis[i]);

}

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

{

scanf("%d",&wi[i]);

}

memset(is,0,sizeof(is)/sizeof(int));

is[0][7500]=1;

ZeroOnepack();

printf("%d\n",is[G][7500]);

return 0;

}

2)用一维数组 01背包解。须用2个一维数组以保证一个物体只能用一次，
因为：假如说只用到f这个数组，不用两个：那么讨论到第i个物体的时候，
f[j]是一个用了i这个物体来达到的状态，但是你f[k]是用f[j]来转移并且用上i的话，
这样f[k]就用了两次i了。二维数组就可以避免这种重复使用，或者用两个一维
数组，每次保证累加时使用的都是没用i时的：当我讨论到i这个物体的时候，先
把之前没讨论到i的状态先存下来，这样每到达一个新状态，都是用没有用到i的
状态tp来转移的，这样的新状态都是用了一次i

//2)用一维数组 01背包解。须用2个一维数组以保证一个物体只能用一次，

//因为：假如说只用到f这个数组，不用两个：那么讨论到第i个物体的时候，

//f[j]是一个用了i这个物体来达到的状态，但是你f[k]是用f[j]来转移并且用上i的话，

//这样f[k]就用了两次i了。二维数组就可以避免这种重复使用，或者用两个一维

//数组，每次保证累加时使用的都是没用i时的：当我讨论到i这个物体的时候，先

//把之前没讨论到i的状态先存下来，这样每到达一个新状态，都是用没有用到i的

//状态tp来转移的，这样的新状态都是用了一次i

#include<cstdio>

#include<string>

#include<iostream>

#include<cstdlib>

int dp[15002],tp[15002],C,G;

int main()

{

int i,j,k,pos[26],wi[26];

scanf("%d%d",&C,&G);

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

scanf("%d",&pos[i]);

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

scanf("%d",&wi[i]);

dp[7500]=1;

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

{

memcpy(tp,dp,sizeof(dp));

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

for(j=-7500;j<=7500;j++)

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

dp[j+7500]+=tp[j+7500-pos[k]*wi[i]];

}

printf("%d\n",dp[7500]);

return 0;

}

posted @ 2011-08-02 08:34 拥梦的小鱼阅读(957) | 评论 (1) | 编辑收藏

重踏征程

      有人说：一心想着自己目标前进的人，整个世界都会给他让路。我已经颓然很久了，放暑假这么长时间，一直在浑浑噩噩的度过，其实，确实是缺少一个目标来指引，让我焕发出勃勃斗志啊！决定不转专业后，总是被各种其他琐碎的事情纠缠，无论是亲情、友情还是爱情，是的，这些都还是很重要，但是，我渐渐明白，感情的事，很多时候不是一个人瞎猜测，空想，不敢面对，就可以解决的。7月份，我把我该做的已经差不多都做了，其他的也只能静观其变，我会坚强勇敢的面对可能发生的一切！8月份，是新的开始，也应该好好审视一下自己，做个长远的规划了。
      来学校也好几天了，第二天去实验室溜达了一圈，在里面如坐针毡的难受。我怕自己做错决定，怕自己全忘光了，怕从头开始，怕坚持不到最后……这一切的怕都是多么可笑，还没开始有什么好怕的，每天上人人，QQ就很充实，什么都不用干，就很快乐，就不用怕了?这种怕一个人呆着，只能在网上消磨时光，在人群中驱散孤独的日子，才是我真正厌恶的！我决定了，还是投身于ACM吧！尽管已经很晚了，但这个一直很吸引我，而且不开始就放弃，不算很可惜吗？我会全力以赴奋斗到底的！大牛学长说，要先给自己确定个目标才好啊！刚查了百度知道的规划：

1、做了多少水题了，400道以上，反正是打基础，越多越好，没事儿就做做。
2、对于学习数据结构和算法，我认为到网上找经典的题目，最好找有分类功能的OJ，ACM.NUDT.EDU.CN，国防科大的OJ有分类功能，找到题目了解题意后到网上收集解题报告读解题报告和标准程序了解数据结构和算法的思想，记住真正的理解了才是最好的。然后按照脑袋里学习到的思想去敲自己的程序，如果有不懂就要去问别人。
3、拜师，我认为拜师这应该是非常重要的。有个师傅总归是好的，不要拉不下面子，面子没得知识来得贵重。
4、真正热爱编程不仅限于ACM。
5、加入ACM-DIY群，随时了解各大OJ是否举办有月赛之类的比赛，做完比赛后，不会做的题目就拉到那些做出来的人问，要能扯下脸皮来，然后把算法学到。
6、多认识人，最重要的是多认识些牛人和与你同等实力的选手。
7、建立自己的阶段目标，比如说要超越那些选手，要超越哪些比自己强的组。
8、关心你们学校ACM组队的动态，随时关心集训队的新闻；加刘汝佳校内，随时了解国内ACM方面的动态。
9、知识是一点一点积累起来的，不要好高骛远。一个问题一个问题的解决。
10、最后祝你成为真正的ACMer~~~~

      结合我的情况，就先超越sll,再是ZYD吧，然后争取早日跟CY他们一个级别。就先这样吧。每天要刷5到10道题目。这个暑假说什么也得先把题目刷到400以上！那么放假期间就得每天刷十多道题目呢。。加油！好好干！

      第二件事，想做的，是想把高级口译拿下。这个口语真是头疼了~TOEFL全砸它手里了。不行，我要好好地再练练口语，背完新概念3、4。如果有时间的话，打算在步入正轨后学习下法语。

      业余的时候，还是多看看书吧。我好喜欢读书的呀，怎么越长大越没时间读了呢，这可不行？宁愿肉体挨饿，也不能让精神缺乏营养。奋斗吧！

      加油！


         黄沙百战穿金甲，
                    不破楼兰终不还！

posted @ 2011-08-01 13:26 拥梦的小鱼阅读(231) | 评论 (0) | 编辑收藏

成长推荐偱路

学习算法之路

1人收藏此文章，收藏此文章发表于11个月前 , 已有433次阅读共1个评论 1人收藏此文章

第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，

因为太常用，所以要练到写时不用想，10-15 分钟内打完，甚至关掉显示器都可以把程序打

出来.

1.最短路(Floyd、Dijstra,BellmanFord)

2. 最小生成树(先写个prim,kruscal要用并查集，不好写)

3.大数（高精度）加减乘除

4.二分查找. (代码可在五行以内)

5.叉乘、判线段相交、然后写个凸包.

6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)

7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.

8. 调用系统的qsort, 技巧很多，慢慢掌握.

9. 任意进制间的转换

第二阶段：练习复杂一点，但也较常用的算法。

如：

1. 二分图匹配（匈牙利），最小路径覆盖

2. 网络流，最小费用流。

3. 线段树.

4. 并查集。

5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp

6.博弈类算法。博弈树，二进制法等。

7.最大团，最大独立集。

8.判断点在多边形内。

9. 差分约束系统.

10. 双向广度搜索、A*算法，最小耗散优先.

HDU1072_bfs+剪枝 contest9_A

摘要: NightmareTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2625 Accepted Submission(s): 1313 Problem D... 阅读全文

posted @ 2011-06-05 00:23 拥梦的小鱼阅读(322) | 评论 (0) | 编辑收藏

POJ3278_bfs简单题

/*

bfs+剪枝典型简单题，注意此题设置的方向动态确定，且要判断，是否左大于右。

*/

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <memory.h>

#include <cmath>

#include <bitset>

#include <queue>

#include <vector>

using namespace std;

const int MAXN =100400;

const int INF =0x4ffffff;

#define CLR(x,y) memset(x,y,sizeof(x))

#define ADD(x) x=((x+1)&BORDER)

#define IN(x) scanf("%d",&x)

#define OUT(x) printf("%d\n",x)

#define MIN(m,v) (m)<(v)?(m):(v)

#define MAX(m,v) (m)>(v)?(m):(v)

#define ABS(x) ((x)>0?(x):-(x))

struct node{

int x;

int step;

node():x(0),step(0){}

};

int vis[MAXN*2];

int sum,n,ans;

int main()

{

int n,k,i,min=999999;

int dir[4]={-1,1};

node start,end,tmp,next;

queue<node> que;

scanf("%d%d",&start.x,&end.x);

que.push(start);

vis[start.x]=1;

if(start.x>end.x)min=start.x-end.x;

else

while(!que.empty())

{

tmp=que.front();

que.pop();

dir[2]=tmp.x;

//dir[3]=2*tmp.x;

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

{

next.x=tmp.x+dir[i];

if(next.x>=0&&next.x<=end.x*3&&next.x<=MAXN&&tmp.step<min&&!vis[next.x])

{

next.step=tmp.step+1;

if(next.x==end.x)min=min>next.step?next.step:min;

que.push(next);

vis[next.x]=1;

}

memset(vis,0,sizeof(vis));

if(min==999999)min=0;

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

min=999999;

}

Catch That Cow

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 23446		Accepted: 7185

Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input

5 17

Sample Output

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

posted @ 2011-06-05 00:19 拥梦的小鱼阅读(483) | 评论 (0) | 编辑收藏

希望的海洋

导航

留言簿(1)

随笔分类

随笔档案

阅读排行榜

评论排行榜

常用链接

统计

最新评论

简易DP——最长上升子序列 poj 2533

递归深搜——poj 1321,类八皇后

POJ题目分类

背包系列 POJ——1276 多重背包

不知道做什么时的任务

背包系列——poj 1837

重踏征程

成长推荐偱路

学习算法之路

HDU1072_bfs+剪枝 contest9_A

POJ3278_bfs简单题