-
dp专题
互不侵犯的king状压dp题每一行放不放国王可以用1010010来表示所以每一行的状态可以看成一个二进制数这样n是小于9的，可以把小于2^n，（因为2^9是512，很小）的数打表存出来把自己和自己冲突的筛掉，然后记下有多少1，判断他们是否冲突。预处理完了，接下来是dp了动态转移方程：dp[i][q+t[j]][a[j]]=Σdp[i-1][q][a[i]]123456789101112131415 …
-
子串
这个题我搞了好久，终于算是明白了点吧看了很多大神的博客，总结出来了一些做法，不知对不对，就写一些吧。先定义两个数组sum[i][j][k]就是a串前i个字母,b串前j个字母的方案总数！！！！，就是结果f[i][j][k]是用第i个字母用的方案数。当匹配时：因为第i个可以和前i-1合并为一块(但这是方案数不变,因为组数相同，为f[i-1][j-1][k]),也可以不合并,（为sum[i-1][j-1 …
-
书的复制
这个题就是一个动归，和乘积最大一样，处理前缀和，枚举当前位置和划分层数，找最大的时间，取最小值12345678910111213141516171819202122232425262728293031323334353637383940#include<cstdio>#include<iostream>#include<cstring>using namespa …
-
最长公共子序列
最长公共子序列（lcs）到最长上升子序列（lis）的转化。把第一个串的元素，转化为第二个串的位置，再倒过来，找最长上升子序列。别问我为什么，我也不知道。。。。。 简单说明：上面的序列和最长公共子串是等价的。对于一个满足最长严格递增子序列的序列，该序列必对应一个匹配的子串。反序是为了在递增子串中，每个字母对应的序列最多只有一个被选出。反证法可知不存在更大的公共子串，因为如果存在，则求得的最长递增子序 …
-
低价购买
第一问很好做，就是一个很简单的dp求最长下降子序列。第二问就有一些问题了，怎么找最大的方案数呢？那就需要看状态了，i位置的方案数只能由比他小一的位置转移过来，而且每一个都能转移过来，所以说因为第一问求出f[i]了所以递推方程式为 t[i]=∑t[j] (f[j]+1=f[i])但还有一个问题，不能重复，如果有相同的情况，就可以把后面的方案数去掉，因为不可能是最优解，这样就不重复了。1234567 …
-
二维费用的背包
12345678910111213141516171819202122232425262728293031323334#include<cstdio>#include<cmath>#include<iostream>#include<cstring>using namespace std;int f[999][999];int m,n,k;int w …
-
能量项链
1234567891011121314151617181920212223242526272829303132#include<cstdio>#include<iostream>using namespace std;int n;int f[1999][1999];int a[9999];int ans;int max1=-999999999;int main(){ …
-
合唱队形
12345678910111213141516171819202122232425262728293031323334353637383940#include<cstdio>#include<iostream>using namespace std;int m,n;int f[9999],f2[9999],h[9999]; int maxn=-9999;int main() …
-
乘积最大
简单的搜索12345678910111213141516171819202122232425262728293031#include<cstdio>#include<iostream>using namespace std;int k;int s[1999][1999],a[9999];int tot=-999;int m,n;int dfs(int x,int k,int …
-
导弹拦截
求一个最长上升子序列，一个最大下降子序列，输出就OK了，写了个dfs没过12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include<cstdio>#include<iostream> …