黑书 p116页上有详细的分析 代码 如下： #include <iostream> #include <math.h> using namespace std; int grid[8][8]; int d[16][9][9][9][9]; int sm[9][9]; int const INF=10000000; int n; int sum(int i,int j,int s,int t) { return sm[s][t]-sm[i][t]-sm[s][j]+sm[i][j]; } int comp(int a,int b,int c) { ...

着道题看起来是一个三维的背包问题,但是注意一个条件,就是每个组件只能放在地x到第x+w的位子上所以这时问题就可以简化复杂度,即只对第i个组件在第x位置上时的价值为j时的f最大值求解。 方程为 f[i][L][C]=max{f[i-1][L][C],f[i-1][L-w][C-c]+F[i]且L-w=x}; 还要注意个地方就是dp的顺序，x越小越i值越小 #include <iostream> #include <algorithm> using namespace std; int l,n,b; //int x,w,f,c; int F[1001][1...

1.先作出这个数的常规意义下的所有因子,再验证这些因子是否满足特定的素因子的条件. 2.用线形筛法筛出可能的素因子,hash或者二分查找. #include <iostream>#include <algorithm>using namespace std; int a[300001];int ans[60000];void prime(int n){ a[0]=1; a[1]=1; for(int i=2;i*i<=n;i++) { if(a[i]==0&amp;&amp;(i%7==1||i%7==6)) { for(int j=i*i;j<=n;j+...

这道题是最长上升序列。 由于给出的数据量过大，不能直接使用dp的方法来去最长升序，因为这样的时间为0（n^2） 下面我们考虑如下的情况： 对于第i个数来说他是否是1……i的最长上升序列的元素，就是在1……i-1中的最长上升序列最后一个值比f[i]小，那么f[i]元素就为1……i上的最长上升序列的元素。 如过不存在1……i-1的最长上升序列满足上述情况时，我们不能直接认为i就1……n上的最长升序列。这是我们可以这样的假设，假设f[i]是1……n的最长生序列的元素。那么f[i]在1……n的最长升序列的位置应该在1……i-1的最长生序列中比f[i]小的最大的元素...

01背包问题; 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是: F[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]};f[i-1][v-c[i]]+w[i]表示在第i-1个背包在v-c[i]的容量下的价值+第i件物品的价钱。 在背包问题中，时间为O(NV)没办法优化，但是在空间上是可以优化的。可以...