[综合] 51nod 循环数组最大子段和

这个问题就是在原来的基础上加上了可以循环。 那么我们可以分两种情况处理，一种是有从尾到头的，例如1表示取，0表示不取，则是11000011 一种是没有跨越的，即000111100 那么对于第二种情况可以直接用最大字段和做，关键是第一段要怎么处理。 这里需要用到逆向思维，在1110000111这一个答...

[综合] 51nod 多重背包问题（二进制优化）

有N种物品，每种物品的数量为C1，C2......Cn。从中任选若干件放在容量为W的背包里，每种物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数）。求背包能够容纳的最大价值。 我们可以转化成01背包来做，但是这样很慢。 所以我们可以二进制...

[综合] 51nod 子序列的个数 （动规分析方法）

这道题的分析方法我很需要学习学习。 一开始我想的是f[i][j]表示前i个数子序列长度为j的个数 然后发现新加入一个数的时候会和前面的重复，这个时候不知道该怎么处理这种重复。 其实我再继续往下想就可以想到，这些重复的序列都有一个特征，结尾都是新加入的这个数 那么这就启示我们可以利用前面算出的结果来算...

[综合] caioj 1063 动态规划入门（一维一边推1：美元和马克）

这道题一开始我是这么想的 最后的答案肯定是某次的马克换回来的，但这个该怎么确定？？ 实际上应该把范围缩小，只看最后一次和倒数第二次之间有什么联系。 可以发现，只有两种可能，最后一天换或者不换。换的话就要求出 最后一天之前最多的马克，不换的话就是最后一天前最多的美元。 设d[i]为前i次最多的美元，m...

[综合] caioj 1065 动态规划入门（一维一边推3：合唱队形）

就是最长上升子序列，但是要用n^2的算法。 #include<cstdio> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;constintMAXN=1123...

[综合] caioj 1067动态规划入门（一维一边推5： 乘积最大(高精度版））

因为这里涉及到乘号的个数，那么我们可以用f[i][j]表示前i个位乘号为j个时的最大乘积 那么相比上一题就是多了一层枚举多少个乘号的循环，可以得出 f[i][r]=max(f[j-1][r-1],num(j,i)); num(j,i)表示第j位到第i位的数，j<i 然后注意要用高精度来计算。 ...

[综合] caioj 1069 动态规划入门（二维一边推2：顺序对齐）（最长公共子序列拓展总结）

caioj1068是最长公共子序列裸体，秒过，就不写博客了 caioj1069到1071都是最长公共字序列的拓展，我总结出了一个模型，屡试不爽（１）字符串下标从1开始，因为０用来表示字符为空的情况，而不是第一个字符（２）初始化问题。一般设f[i][j]为第一个字符前ｉ个，第二个字符前ｊ个的最优价值f...

[综合] caioj 1070 动态规划入门（二维一边推3：字符距离）（最长公共子序列拓展）

复制上一题总结 caioj1069到1071都是最长公共字序列的拓展，我总结出了一个模型，屡试不爽（１）字符串下标从1开始，因为０用来表示字符为空的情况，而不是第一个字符（２）初始化问题。一般设f[i][j]为第一个字符前ｉ个，第二个字符前ｊ个的最优价值f[0][0]=0然后要初始化f[i][0],...

[综合] caioj 1071 动态规划入门（二维一边推4：相似基因） （最长公共子序列拓展）

复制上一题总结 caioj1069到1071都是最长公共字序列的拓展，我总结出了一个模型，屡试不爽（１）字符串下标从1开始，因为０用来表示字符为空的情况，而不是第一个字符（２）初始化问题。一般设f[i][j]为第一个字符前ｉ个，第二个字符前ｊ个的最优价值f[0][0]=0然后要初始化f[i][0],...

[综合] caioj 1073 动态规划入门（三维一边推：最长公共子序列加强版（三串LCS））

三维的与二维大同小异，看代码。 #include<cstdio> #include<cstring> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd...

[综合] caioj 1074 动态规划入门（中链式1：最小交换合并问题）

经典的石子合并问题！！！ 设f[i][j]为从i到j的最大值 然后我们先枚举区间大小，然后枚举起点终点来更新 f[i][j]=min(f[i][k]+f[k+1][j]+sum(i,j)); 最后f[1][n]就是答案！！ #include<cstdio> #include<cst...

[综合] caioj 1075 动态规划入门（中链式2：能量项链）（中链式dp总结）

我又总结了一种动归模型…… 这道题和上一道题很类似，都是给一个序列，然后相邻的元素可以合并 然后合并后的元素可以再次合并 那么就可以用这两道题类似的方法解决 简单来说就是枚举区间，然后枚举断点 加上断点左右两边的值（按照题目，可能不是加），然后在按题目加上计算合并后总的序列的值 就这一道题而言f[i...

[综合] caioj 1076 动态规划入门（中链式3：最大的算式）

一开始写了一个复杂度很大的方法，然后还过了（千万记得开longlong） #include<cstdio> #include<cstring> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i...

[综合] caioj 1077 动态规划入门（非常规DP1：筷子）

首先可以看出排序之后，最优解肯定是每一对都相邻才是最优的那么我们就要找构成最优解的相邻组设f[i][j]是前i个字符，k对的最小值如果当前这个筷子不取的话，f[i][j]=f[i-1][j]如果取的话f[i][j]=f[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1])取最小...

[综合] caioj 1078 动态规划入门（非常规DP2：不重叠线段）（状态定义问题）

我一开始想的是前i个区间的最大值显然对于当前的区间，有不选和选两种情况如果不选的话，就继承f[i-1]如果选的话，找离当前区间最近的区间取最优f[i]=max(f[i-1,f[j]+a[i].v())j为i前面区间中能取得离i最近的区间那么显然这里涉及到f[i]的时候取的最后一个区间是什么，才能比较...

[综合] caioj 1079 动态规划入门（非常规DP3：钓鱼）(动规中的坑)

这道题写了我好久，交上去90分，就是死活AC不了 后来发现我写的程序有根本性的错误，90分只是数据弱 #include<cstdio> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingn...

[综合] 关于memset赋最值

出处[辗转山河弋流歌by空灰冰魂] blog.csdn.net/vmurder/article/details/46537613 memset(a,0x3f,sizeof(a))//int,到1e9左右,相加不会溢出memset(a,0xc0,sizeof(a));//int-1e9同上memset...

[综合] caioj 1080 动态规划入门（非常规DP4：乘电梯）(dp数组更新其他量)

我一开始是这么想的注意这道题数组下标是从大到小推，不是一般的从小到大推f[i]表示从最高层h到第i层所花的最短时间，答案为f[1]那么显然f[i]=f[j]+wait(j)+(j-1),j>i也就是说枚举从哪个楼层过来。取最优wait（j）表示从第j个楼层等待电梯的最短时间。这个算法应该是正确...

[综合] caioj 1082 动态规划入门（非常规DP6：火车票）

f[i]表示从起点到第i个车站的最小费用 f[i]=min(f[j]+dist(i,j)),j<i 动规中设置起点为0，其他为正无穷 （貌似不用开longlong也可以） #include<cstdio> #include<algorithm> #defineREP(i...

[综合] caioj 1083 动态规划入门（非常规DP7：零件分组）（LIS）

这道题题目给的顺序不是固定的所以一开始要自己排序，按照w来排序后来只要看l就可以了然后求最长下降子序列即可（根据那个神奇的定理，LIS模板里有提到） #include<cstdio> #include<algorithm> #include<cstring> #d...