背包问题、LIS及LCS.doc

poj 1837 Balance （01背包变形）分类：DP(动态规划)2014-05-20 15:56134人阅读评论(0)收藏编辑删除BalanceTime Limit:1000MSMemory Limit:30000KTotal Submissions:10065Accepted:6231DescriptionGigel has a strange balance and he wants to poise it. Actually, the device is different from any other ordinary balance.It orders two arms of negligible weight and each arms length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 = G = 20) knowing that these weights have distinct values in the range 1.25. Gigel may droop any weight of any hook but he is forced to use all the weights.Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced.Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device.It is guaranteed that will exist at least one solution for each test case at the evaluation.InputThe input has the following structure: the first line contains the number C (2 = C = 20) and the number G (2 = G = 20); the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15.15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis (when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the hook is attached: - for the left arm and + for the right arm); on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1.25 representing the weights values.OutputThe output contains the number M representing the number of possibilities to poise the balance.Sample Input2 4-2 3 3 4 5 8Sample Output2一个天平有若干个挂钩和砝码，求把砝码全用上的使天平平衡的方法数目。因为位置有负值，而15*20*25=7500，所以可以令dp07500=1,(j=7500代表平衡状态)状态转移方程为：dpij+gi*ck+=dpi-1j; 即达到当前状态的数目有多少。#includestdio.h#includestring.h#define mmin(a,b) (a)(b)?(a):(b)#define N 15005int dp22N;int main() int i,j,k,n,m; int c25,g25; while(scanf(%d%d,&n,&m)!=-1) for(i=1;i=n;i+) scanf(%d,&ci); for(i=1;i=m;i+) scanf(%d,&gi); memset(dp,0,sizeof(dp); dp07500=1; /不挂砝码时平衡状态有一种 for(i=1;i=m;i+) for(j=0;jN;j+) if(dpi-1j=0) /该状态不可达 continue; for(k=1;k=n;k+) dpij+gi*ck+=dpi-1j; printf(%dn,dpm7500); return 0;bnu 沙漠之旅 （二维背包）分类：DP(动态规划)2014-05-23 16:09197人阅读评论(0)收藏编辑删除目录(?)+沙漠之旅Time Limit:1000msMemory Limit:655“小胖要穿越一片沙漠，小胖开着一辆大吉普，小胖的吉普油耗高，吉普能放四桶油。”这就是人人会唱的沙漠之歌体现了小胖拔群的聪明才智。小胖的问题是这样的：现在需要驾车穿越一片沙漠，总的行驶路程为L。小胖的吉普装满油能行驶X距离，同时其后备箱最多能放下四桶油。在起点有N种汽油，每种汽油都有无限桶，一桶能行驶距离Ai。现在小胖想知道：能不能恰好带四桶油，再加上出发前装满的油，使得恰好能行驶L距离。Input第一行一个正整数T（1 = T = 50），表示数据的组数。接下来T组数据，每组数据的第一行是三个整数L（1 = L = 1000），X（1 = X = L），N（1 = N = 1000）。接下来N行，每行一个正整数Ai（1 = Ai = 1000），表示第i种汽油一桶能行驶的距离。Output对于每组数据输出一行，若能输出“Yes”，否则输出“No”Sample Input120 9 223Sample OutputYes二维背包#include#include#define N 1005#define inf 10000000const int M=5;int fNM,aN;int max(int a,int b)return ab?a:b;int main()int i,j,k,l,T,n;int x;scanf(%d,&T);while(T-)scanf(%d%d%d,&l,&x,&n);l-=x;for(i=0;i=l;i+)for(j=0;jM;j+)fij=-inf;f00=0; for(i=0;in;i+)scanf(%d,&ai);for(i=0;in;i+)for(j=ai;j=l;j+)for(k=1;k=M-1;k+) /个数的限制，必须装四桶for(x=1;x=k&x*aib?a:b;void zero(int c,int w)int i;for(i=v;i=c;i-)fi=max(fi,fi-c+w);void comple(int c,int w)int i;for(i=c;i=v)comple(c,w);elseint k=1;while(knum) /小于等于zero(k*c,k*w);num-=k;k*=2;zero(num*c,num*w);int main()int i,Case=1;while(scanf(%d,&num1)v=num1;for(i=2;i=6;i+)scanf(%d,&numi);v+=numi*i;if(v=0)break;printf(Collection #%d:n,Case+);if(v%2=1)printf(Cant be divided.nn);continue;v/=2;memset(f,0,sizeof(f);for(i=1;i7;i+)if(numi=0)continue;multi(i,i,numi);int flag=0;if(fv=v)printf(Can be divided.nn);elseprintf(Cant be divided.nn);return 0;poj 1276 Cash Machin（混合背包）分类：DP(动态规划)2013-12-23 22:01392人阅读评论(0)收藏编辑删除Cash MachineTime Limit:1000MSMemory Limit:10000KTotal Submissions:25941Accepted:9139DescriptionA Bank plans to install a machine for cash withdrawal. The machine is able to deliver appropriate bills for a requested cash amount. The machine uses exactly N distinct bill denominations, say Dk, k=1,N, and for each denomination Dk the machine has a supply of nk bills. For example,N=3, n1=10, D1=100, n2=4, D2=50, n3=5, D3=10means the machine has a supply of 10 bills of 100 each, 4 bills of 50 each, and 5 bills of 10 each.Call cash the requested amount of cash the machine should deliver and write a program that computes the maximum amount of cash less than or equal to cash that can be effectively delivered according to the available bill supply of the machine.Notes: is the symbol of the currency delivered by the machine. For instance, may stand for dollar, euro, pound etc.InputThe program input is from standard input. Each data set in the input stands for a particular transaction and has the format:cash N n1 D1 n2 D2 . nN DNwhere 0 = cash = 100000 is the amount of cash requested, 0 =N = 10 is the number of bill denominations and 0 = nk = 1000 is the number of available bills for the Dk denomination, 1 = Dk = 1000, k=1,N. White spaces can occur freely between the numbers in the input. The input data are correct.OutputFor each set of data the program prints the result to the standard output on a separate line as shown in the examples below.Sample Input735 3 4 125 6 5 3 350633 4 500 30 6 100 1 5 0 1735 00 3 10 100 10 50 10 10Sample Output73563000解题思路：用混合背包解决，学习背包可以看看背包9讲#include#include#include#include#define N 100005int m,fN;int Max(int a,int b)return ab?a:b;void Zeroone(int c,int w) / 01背包int i;for(i=m;i=c;i-)fi=Max(fi,fi-c+w);void Comple(int c,int w) /完全背包int i;for(i=c;i=m)Comple(c,w);elseint i=1; /二进制思想，用一些数表示所有可能的组合。while(inum)Zeroone(i*c,i*w); /如num=13，可以用1，2,4,6表示所有组合num-=i;i*=2;Zeroone(c*num,w*num);int main()int i,n;int num1005,cost1005;while(scanf(%d,&m)!=EOF)memset(f,0,sizeof(f);scanf(%d,&n);for(i=0;in;i+)scanf(%d%d,&numi,&costi);for(i=0;in;i+)Multi(costi,costi,numi);printf(%dn,fm);return 0;LIS系列问题（hdu 4521、poj 3903）分类：DP(动态规划)2014-10-21 13:1895人阅读评论(0)收藏编辑删除小明系列问题小明序列Time Limit: 3000/1000 MS (Java/Others)Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1848Accepted Submission(s): 564Problem Description大家都知道小明最喜欢研究跟序列有关的问题了，可是也就因为这样，小明几乎已经玩遍各种序列问题了。可怜的小明苦苦地在各大网站上寻找着新的序列问题，可是找来找去都是自己早已研究过的序列。小明想既然找不到，那就自己来发明一个新的序列问题吧！小明想啊想，终于想出了一个新的序列问题，他欣喜若狂，因为是自己想出来的，于是将其新序列问题命名为“小明序列”。提起小明序列，他给出的定义是这样的：首先定义S为一个有序序列，S= A1 , A2 , A3 , . , An ，n为元素个数 ；然后定义Sub为S中取出的一个子序列，Sub= Ai1 , Ai2 , Ai3 , . , Aim ，m为元素个数 ；其中Sub满足 Ai1 Ai2 Ai3 . Aij-1 Aij Aij+1 . d (1 j = m， d为给定的整数)；显然满足这样的Sub子序列会有许许多多，而在取出的这些子序列Sub中，元素个数最多的称为“小明序列”(即m最大的一个Sub子序列)。例如：序列S=2,1,3,4 ，其中d=1；可得“小明序列”的m=2。即Sub=2,3或者2,4或者1,4都是“小明序列”。当小明发明了“小明序列”那一刻,情绪非常激动，以至于头脑凌乱，于是他想请你来帮他算算在给定的S序列以及整数d的情况下，“小明序列”中的元素需要多少个呢？Input输入数据多组，处理到文件结束;输入的第一行为两个正整数 n 和 d；(1=n=105 , 0=d=105)输入的第二行为n个整数A1 , A2 , A3 , . , An，表示S序列的n个元素。(0=Ai=105)Output请对每组数据输出“小明序列”中的元素需要多少个，每组测试数据输出一行。Sample Input2 01 25 13 4 5 1 25 23 4 5 1 2Sample Output221一个求最长上升子序列变形的问题，限制条件要求相邻两项的下标差值必须大于d。c数组存储当前可用的值。#include#include#include#includeusing namespace std;#define N 100005const int inf=0x1f1f1f1f;int aN,cN,dpN;int n,d;int findd(int x) int l,r,mid; l=0; r=n-1; while(l1; if(cmidx) l=mid+1; else r=mid-1; return l;int solve() int i,j,ans=0; for(i=0;i=0&cdpjaj) cdpj=aj; return ans;int main() while(scanf(%d%d,&n,&d)!=-1) for(int i=0;in;i+) scanf(%d,&ai); ci=inf; printf(%dn,solve()+1); return 0;Stock Exchange（LIS）Time Limit:1000MSMemory Limit:65536KTotal Submissions:4405Accepted:1555DescriptionThe world financial crisis is quite a subject. Some people are more relaxed while others are quite anxious. John is one of them. He is very concerned about the evolution of the stock exchange. He follows stock prices every day looking for rising trends. Given a sequence of numbers p1, p2,.,pn representing stock prices, a rising trend is a subsequence pi1 pi2 . pik, with i1 i2 . ik. Johns problem is to find very quickly the longest rising trend.InputEach data set in the file stands for a particular set of stock prices. A data set starts with the length L (L 100000) of the sequence of numbers, followed by the numbers (a number fits a long integer).White spaces can occur freely in the input. The input data are correct and terminate with an end of file.OutputThe program prints the length of the longest rising trend.For each set of data the program prints the result to the standard output from the beginning of a line.Sample Input6 5 2 1 4 5 3 3 1 1 1 4 4 3 2 1Sample Output3 1 1HintThere are three data sets. In the first case, the length L of the sequence is 6. The sequence is 5, 2, 1, 4, 5, 3. The result for the data set is the length of the longest rising trend: 3.需要O(n*(logn)的算法才能过：即假设数组元素 axayai,xyclen,则把ai值接到clen后面得到一个更长的序列。否则，在数组c里查找当前值所在的位置，并把当前值ai替换掉查找到的值x，ai=x;#include#include#includeusing namespace std;#define N 100005const int inf=0x1f1f1f1f;int aN,cN;int main()int i,n,len;while(scanf(%d,&n)!=-1)for(i=0;in;i+)scanf(%d,&ai);c0=-inf;len=0;for(i=0;iclen) c+len=ai; else int l=0,r=len,mid; while(l1; if(cmidai) l=mid+1; else r=mid-1; cl=ai; printf(%dn,len);return 0;poj 2127 Greatest Common Increasing Subsequence（LCIS）分