[综合] 紫书 习题 10-44 UVa 11246 ( 容斥原理）

把k的倍数的删去（k,2k,3k……），但是k^2不应该删去，因为k已经删去，所以不存在某个数乘上k之后为k^2 所以k^2可以留下，然后因为有k^2，所以k^3就是k^2的k倍，所以k^3要删去，但是k^4又要加回来，以此类推 ans=n-n/k+n/(k^2)-n/(k^3)…… 见代码 #in...

[综合] 紫书 例题 9-1 UVa 1025 ( DAG的动态规划）

影响到状态的只有时间和在哪个车站（空间），所以可以设f[i][j]是时刻i的时候在第j个车站的最少等待时间 因为题目中的等待时间显然是在0时刻1车站，所以答案为f[0][1]，那么就提醒我们从大推到小，然后可以发现d[T][n]一定等于0，所以这个可以作为边界条件。同时时刻0的每一个车站都是正无穷，...

[综合] 紫书 例题 9-2 UVa 437 ( DAG的动态规划）

很明显可以根据放不放建边，然后最一遍最长路即是答案 DAG上的动态规划就是根据题目中的二元关系来建一个 DAG，然后跑一遍最长路和最短路就是答案，可以用记忆化搜索的方式来实现 细节：（1）注意初始化数组 （2）搜索的过程中最后记住加入状态本身的值，不然会答案全部为0 #include<cstd...

[综合] 紫书 例题 9-3 UVa 1347 ( 状态设计）

首先做一个转化，这种转化很常见。题目里面讲要来回走一遍，所以就转化成两个从起点到终点，路径不重合那么很容易想到用f[i][j]表示第一个走到i，第二个人走到j还需要走的距离但是这里无法保证路径不重合，所以这里怎么设计状态很关键。我们设f[i][j]是1到max(i,j)全部走过，同时第一个在i，第二...

[综合] 紫书 例题 9-4 UVa 116 ( 字典序递推顺序）

这道题在递推方式和那个数字三角形有一点相像，很容易推出来但是这道题要求的是字典序，这里就有一个递推顺序的问题这里用逆推，顺推会很麻烦，为什么呢？如果顺推的话，最后一行假设有种情况是最小值，那么你怎么知道哪一种的是字典序最小？最后一行的数字最小显然不一定整个路径的字典序最小，因为字典序是从第一行开始比...

[综合] 紫书 例题 9-5 UVa 12563 ( 01背包变形）

总的来说就是价值为1，时间因物品而变，同时注意要刚好取到的01背包（1）时间方面。按照题意，每首歌的时间最多为t+w-1，这里要注意。同时记得最后要加入时间为678的一首歌曲（2）这里因为要输出时间，也就是重量，那么这个时候初始化就要注意了。因为如果只是输出价值的话就全部初始化为0，但是要输出重量，...

[综合] 紫书 例题 9-6 UVa 11400 (线性结构上的动态规划）

这道题的下标从1开始比较方便，一方面前缀和算的方便一些，一方面涉及到前j 个灯泡，那么如果从0开始，前3个灯泡就是第0,1,2,3个，非常奇怪。 所以灵活换下标。 然后这道题的动规有点暴力枚举的意思，在算出前面答案的前提下枚举当前灯泡用多少去更新当前答案 #include<cstdio>...

[综合] 紫书 例题 9-7 UVa 11584 (线性结构上的动态规划）

这道题判断回文串的方法非常的秀！这里用到了记忆化搜索，因为会有很多重复同时用kase来区分每一组数据然后还有用递归来判断回文，很简洁 然后这种线性结构的动态规划的题，就是把当前的这个数组分成两块来枚举，一块是之前已经得出的最优解，一块是自己现在按照题目要求来算出的值，这样枚举下去。然后要注意初始化的...

[综合] 紫书 例题 9-8 UVa 1625 (滚动数组+公共字符串处理）

这题看题解看了很久，学到了挺多（自己还是太弱，唉！） （1）这道题的思路非常的巧妙。我一开始看到就觉得不好来记录开始位置以及 结束位置。但是题解换了一个思路，记录每一次开始了但还没有结束的字符有多少个 这样每次进来一个新的字符，就可以更新答案。 （2）这一类两个字符串取公共部分的题，有一个大概的套路...

[综合] 紫书 例题 9-9 UVa 10003 (区间dp+递推顺序）

区间dp，可以以一个区间为状态，f[i][j]是第i个切点到第j个切点的木棍的最小费用 那么对于当前这一个区间，枚举切点k， 可以得出f[i][j]=min{dp(i,k)+dp(k,j)|i<k<j}+a[j]-a[i]（这一段的长度，也就是这一刀的费用） 然后记住要人为的加入两个切点...

[综合] 紫书 例题 9-10 UVa 1626 (区间dp + 输出技巧）

当前区间f(i,j)分两种情况，一种是s[i]于s[j]符合要求，那么可以转移到f[i+1][j-1]这样答案只会更小或者相等 第二种是直接分成两个部分，即f[i][j]=f[i][k]+f[k+1][j]，这个时候要取min 同时要注意第一种情况未必是最优的，要从一二两种情况里面取最优值 然后输出...

[综合] 紫书 例题 9-11 UVa 1331 (最优三角形剖分）

设置f(i,j)为点i,i+1……j所组成的多边形。 那么可以枚举中间点k,得f(i,j)=min{s(i,j,k),f(i,k),f(k,j)|i<k<j} 当i+1==j，即i与j相邻的时候，f(i,j)=0 在枚举三角形的时候，如果有点在多边形内，则要排除，因为这一部分包括了 多边...

[综合] 紫书 例题 9-12 UVa 12186 (树形dp）

这道题还是比较简单的，对于当前节点，算出每个儿子需要的人数 然后再算出当前节点需要多少个人数，然后排个序加上去就好了。 #include<cstdio> #include<vector> #include<algorithm> #defineREP(i,a,b)f...

[综合] 紫书 例题 9-13 UVa 1220 （最大独立子集）

这里的状态定义的非常的巧妙，d(i,1)表示以i为根节点且选i的子树的最大独立子集 d(i,0)表示以i为根节点且不选i的子树的最大独立子集 d(i,1)=sum{d(v,0)|v是i的儿子} d(i,0)=sum{max(d(v,0),d(v,1))|v是i的儿子} 答案为max（d(0,0),d...

[综合] 紫书 例题 9-14 UVa 1218 （树形dp）

这道题有个初始值设成1e9，然后这个值是要加很多次的，然后就会溢出变成负数，然后就一直WA，找这个bug找了一个小时……以后不能随便这样设那么大，要考虑会不会加很多次然后溢出。 讲一下思路。首先对于当前节点u，可以分三种情况。一种是当前节点是服务器，一种是节点的父亲是服务器，一种是节点的儿子是服务器...

[综合] 51nod 最长公共子序列+输出路径

当x=0或y=0时f[x][y]=0 当a[x]=b[y]时f[x][y]=f[x-1][y-1]+1 当a[x]！=b[y]时f[x][y]=max(f[x][y-1],f[x-1][y]) 注意这里字符串要从1开始，因为转移方程里面0表示这个字符串为空的时候。 动态规划涉及到字符串最好从1开始 ...

[综合] 51nod 编辑距离 + 滚动数组优化

这道题一开始觉得增加和删除会移动字符串的位置很不好做 两个字符串dp状态一般是第一个前i个和第二个前j个 #include<cstdio> #include<algorithm> #include<cstring> #defineREP(i,a,b)for(int...

[综合] 51nod 最大子矩阵和

一个M*N的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。 我们可以降维，枚举矩形的长，然后算出一个一维数组，然后就转化成了最大字段和问题 #include<cstdio> #include<algorithm> #defineREP(i,...

[综合] 51nod 矩阵取数问题

一个N*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。 f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];边界：f[i][0]=0;f[0][i]=0; #include<cstdio>...

[综合] 51nod 最大子段和问题

给出一个整数数组a(正负数都有)，如何找出一个连续子数组（可以一个都不取，那么结果为0），使得其中的和最大？ 用f[i]表示以i为结尾的最大字段和，也就是说i一定要取， 那么f[i]=max(a[i],f[i-1]+a[i]) 只有两种选择，之前的一段取或者不取。 因为只和f[i-1]有关，所以可以...