dp练习。

codevs 1048 石子归并

区间dp

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 using namespace std;

 int f[][],w[],sum[];

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; ch<''||ch>''; ch = getchar()) if (ch=='-') f = -;

     for (; ch>=''&&ch<=''; ch = getchar()) x = x *  + ch - '';

     return x * f;

 }

 int main() {

     memset(f,0x3f,sizeof(f));

     int n = read();

     for (int i=; i<=n; ++i) w[i] = read();

     for (int i=; i<=n; ++i) sum[i] = sum[i-] + w[i];

     for (int i=; i<=n; ++i) f[i][i] = ;

     for (int i=n; i>=; --i) // 枚举顺序：确保下次计算的状态中需要用到的状态已经计算出了。

         for (int j=i+; j<=n; ++j)

             for (int k=i; k<j; ++k)

                 f[i][j] = min(f[i][j],f[i][k]+f[k+][j]+sum[j]-sum[i-]);

     printf("%d\n",f[][n]);

     return ;

 }

codevs  1090 加分二叉树

区间dp

 #include<cstdio>

 int f[][],w[],sum[];

 int rt[][];

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; ch<''||ch>''; ch = getchar()) if (ch=='-') f = -;

     for (; ch>=''&&ch<=''; ch = getchar()) x = x *  + ch - '';

     return x * f;

 }

 void dfs(int l,int r) {

     if (l > r) return ;

     printf("%d ",rt[l][r]);

     dfs(l,rt[l][r]-);

     dfs(rt[l][r]+,r);

 }

 int main() {

     int n = read();

     for (int i=; i<=n; ++i) w[i] = read();

     for (int i=; i<=n; ++i)

             f[i][i] = w[i],rt[i][i] = i;

     for (int i=n; i>=; --i)

         for (int j=i+; j<=n; ++j) // 中序遍历i~j的子树

             for (int t,k=i; k<=j; ++k) { // 枚举根为k

                 if (k==i) t = f[k+][j] + w[k];

                 else if (k==j) t = f[i][k-] + w[k];

                 else t = f[i][k-]*f[k+][j]+w[k];

                 if (t > f[i][j]) f[i][j] = t,rt[i][j] = k;

             }

     printf("%d",f[][n]);

     puts("");

     dfs(,n);

     return ;

 }

openjudge 1768 最大子矩阵

n^3求最大子矩阵

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int a[][],s[][],f[];

 int main () {

     int n;

     scanf("%d",&n);

     for (int i=; i<=n; ++i)

         for (int j=; j<=n; ++j)

             scanf("%d",&a[i][j]);

     for (int j=; j<=n; ++j) // lie

         for (int i=; i<=n; ++i) // hang

             s[j][i] = s[j][i-] + a[i][j];

     int ans = ;

     for (int i=; i<=n; ++i) { // hang1

         for (int j=i; j<=n; ++j) { // hang2

             memset(f,,sizeof(f));

             for (int k=; k<=n; ++k) { // lie

                 f[k] = max(,f[k-])+s[k][j]-s[k][i-];

                 ans = max(ans,f[k]);

             }

         }

     }

     printf("%d",ans);

     return ;

 }

openjudge 8462 大盗阿福

 //f[i]表示到第i家店，的最大价值

 //f[i] = max(f[i=1...i-2]) + a[i]

 //第i次转移与第i+1次转移，只多了f[i-1]，所以记一个变量取出最大值即可

 //网上的另一种转移方程，f数组的意思不变

 //f[i] = max(f[i-1], f[i-2]+a[i]);

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 int a[],f[];

 int main () {

     int T,n;

     scanf("%d",&T);

     while (T--) {

         scanf("%d",&n);

         for (int i=; i<=n; ++i) scanf("%d",&a[i]);

         if (n==) {printf("%d\n",a[]);continue;}

         if (n==) {printf("%d\n",max(a[],a[]));continue;}

         memset(f,,sizeof(f));

         int mx = a[];

         f[] = a[];

         f[] = max(a[],a[]);

         for (int i=; i<=n; ++i) {

             f[i] = mx + a[i];

             mx = max(f[i-],mx);

         }

         int ans = -;

         for (int i=; i<=n; ++i)

             ans = max(ans,f[i]);

         printf("%d\n",ans);

     }

     return ;

 }

openjudge 8464 股票买卖

 //读懂题目，只有两次买卖

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 int a[],f1[],f2[];

 int main () {

     int T,n;

     scanf("%d",&T);

     while (T--) {

         scanf("%d",&n);

         for (int i=; i<=n; ++i) scanf("%d",&a[i]);

         memset(f1,,sizeof(f1));

         memset(f2,,sizeof(f2));

         int mn = a[];f1[] = ;

         for (int i=; i<=n; ++i) {

             f1[i] = a[i] - mn;

             f1[i] = max(f1[i],f1[i-]);

             mn = min(a[i],mn);

         }

         int mx = a[n];f2[n] = ;

         for (int i=n-; i>=; --i) {

             f2[i] = mx - a[i];

             f2[i] = max(f2[i],f2[i+]);

             mx = max(a[i],mx);

         }

         int ans = -;

         for (int i=; i<n; ++i) {

             ans = max(ans,f1[i-]+f2[i]);

         }

         printf("%d\n",ans);

     }

     return ;

 }

openjudge 9268 酒鬼

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 int a[],f[];

 int main () {

     int n;

     scanf("%d",&n);

     for (int i=; i<=n; ++i)

         scanf("%d",&a[i]);

     f[] = a[];

     f[] = a[] + a[];

     //当前酒可以不喝，可以喝一瓶，连续两瓶

     for (int i=; i<=n; ++i)

         f[i] = max(f[i-],max(f[i-]+a[i],f[i-]+a[i-]+a[i]));

     printf("%d",f[n]);

     return ;

 }

openjudge 7614 最低通行费

 //时间是2n-1，所以只能往右或往下走

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 int a[][],f[][];

 int main () {

     int n;

     scanf("%d",&n);

     for (int i=; i<=n; ++i)

         for (int j=; j<=n; ++j)

             scanf("%d",&a[i][j]);

     memset(f,0x3f,sizeof(f));

     f[][] = f[][] = ;

     for (int i=; i<=n; ++i) {

         for (int j=; j<=n; ++j) {

             int shang = f[i-][j],zuo = f[i][j-],aa = a[i][j];

             f[i][j] = min(f[i-][j],f[i][j-]) + a[i][j];

             int ff = f[i][j];

             ff = f[i][j];

         }

     }

     printf("%d",f[n][n]);

     return ;

 }

bzoj 2748 音量调节

 /*

 每个点可以增减一个数，求到最后一个数时的最大价值。

 那么有2^n个选择，2^n显然是超时的。

 但是n<=50, 最大音量也不超过1000，所以可以转化为判定性dp来做。

 到每个点f[i][j]=0/1表示到第i个点j的音量能否达到。

 O(n*MaxLevel) dp

 以空间换时间

 */

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 bool f[][];

 int a[];

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;

     for (; isdigit(ch); ch=getchar()) x=x*+ch-'';

     return x * f;

 }

 int main() {

     int n = read(),s = read(),t = read();

     for (int i=; i<=n; ++i) a[i] = read();

     memset(f,false,sizeof(f));

     f[][s] = true;

     for (int i=; i<=n; ++i) {

         for (int j=; j<=t; ++j) {

             if (j-a[i] >= ) f[i][j] |= f[i-][j-a[i]];

             if (j+a[i] <= t) f[i][j] |= f[i-][j+a[i]];

         }

     }

     int ans=-;

     for (int i=; i<=t; ++i)

         if (f[n][i]) ans = i;

     cout << ans;

     return ;

 }

luogu 1052 过河

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 using namespace std;

 int a[],d[],f[],v[];

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;

     for (; isdigit(ch); ch=getchar()) x = x*+ch-'';

     return x * f;

 }

 int main() {

     int n = read();

     int s = read(),t = read(),m = read();

     for (int i=; i<=m; ++i) a[i] = read();

     sort(a+,a+m+);

     for (int i=; i<=m; ++i)

         d[i] = (a[i]-a[i-])%;

     for (int i=; i<=m; ++i) {

         a[i] = a[i-] + d[i];

         v[a[i]] = ;

     }

     int L = a[m];

     memset(f,0x3f,sizeof(f));

     f[] = ;

     for (int i=; i<=L+t; ++i) {

         for (int j=s; j<=t; ++j) {

             if (i-j>=) f[i] = min(f[i],f[i-j]);

             f[i] += v[i];

         }

     }

     int ans = 1e9;

     for (int i=L; i<=L+t; ++i) ans = min(ans,f[i]);

     cout << ans;

     return ;

 }

bzoj 4300 绝世好题

 /*

 题意：在序列a中求以子序列（不要求连续），满足相邻两位and后不为0，b_i & b_i-1 != 0

 f[i]表示到第i位时的最长长度。f[i] = max(f[j]+1,f[i])，a_i & a_j !=0

 复杂度O(n*n)，超时。 

 换状态表示。

 到第i位的最长长度换一种求法。

 将i化成二进制思考，考虑可以转移到i的j，j必须满足它的二进制有一位和i的二进制同为1

 那么可以dp[x]，表示i以前第x位上为1的所有数中，最长的长度。

 每次用dp[]数组来计算到i的最长长度，然后以i来更新。

 复杂度O(30*n)  

 */

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 using namespace std;

 int b[],f[];

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;

     for (; isdigit(ch); ch=getchar()) x=x*+ch-'';

     return x * f;

 }

 int main() {

     int n = read();

     for (int i=; i<=n; ++i) b[i] = read();

     for (int i=; i<=n; ++i) {

         int mx = ;

         for (int j=; j<=; ++j)

             if (b[i] & (<<j)) mx = max(mx,f[j]);

         for (int j=; j<=; ++j)

             if (b[i] & (<<j)) f[j] = max(f[j],mx+);

     }

     int ans = ;

     for (int i=; i<=; ++i) ans = max(ans,f[i]);

     cout << ans;

     return ;

 }

bzoj 1261 zh_tree

 /*

 因为是中序遍历，中序遍历的性质:任何点都可以做根节点。

 所以枚举根节点即可。

 处理l-r区间，枚举根节点是谁。

 f[l][r][dep]表示l,r区间，根节点的深度是dep，构造成树的最小代价

 那么f[l][r][dep] = min(f[l][k][dep+1]+f[k+1][r][dep+1]+(k*(dep+1)+c)*d[i]/sum)

 转移到两个深度+1的子节点中。

 另一种方法：

 f[l][r]表示l,r区间，构造成树的最小代价。默认根节点的位置是1

 但是转移到的两个子节点的根节点也是1，所以对这两颗子树中的所有点的深度都加1。

 f[l][r] = min(f[l][k]+f[k+1][r]+(c*d[i])/sum) // 子树中的c被子树加上了。

 f[l][r] += k*d[l]/sum + k*d[l+1]/sum +...+ k*d[r]/sum 

 */

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int N = ;

 int n;

 double f[N][N],k,c;

 int sum[N];

 double dfs(int l,int r) {

     if (l > r) return ;

     if (f[l][r] != -) return f[l][r];

     double &ans = f[l][r];

     ans = 1e18;

     for (int i=l; i<=r; ++i)

         ans = min(ans,dfs(l,i-)+dfs(i+,r)+(1.0*c*(sum[i]-sum[i-]))/(1.0*sum[n]));

     ans += (1.0*k*(sum[r]-sum[l-]))/(1.0*sum[n]);

     return ans;

 }

 int main() {

     scanf("%d%lf%lf",&n,&k,&c);

     for (int a,i=; i<=n; ++i) {

         scanf("%d",&sum[i]);sum[i] += sum[i-];

     }

     for (int i=; i<=; ++i)

         for (int j=; j<=; ++j)

             f[i][j] = -;

     printf("%.3lf",dfs(,n));

     return ;

 }

luogu P1970 花匠

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 using namespace std;

 const int N = ;

 int a[N],f[N][];

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;

     for (; isdigit(ch); ch=getchar()) x = x*+ch-'';

     return x * f;

 }

 int main() {

     int n = read();

     for (int i=; i<=n; ++i) a[i] = read();

     f[][] = f[][] = ;

     for (int i=; i<=n; ++i) {

         if (a[i] > a[i-]) {

             f[i][] = f[i-][] + ;

             f[i][] = f[i-][];

         } else if (a[i-] > a[i]) {

             f[i][] = f[i-][] + ;

             f[i][] = f[i-][];

         } else {

             f[i][] = f[i-][];

             f[i][] = f[i-][];

         }

     }

     cout << max(f[n][],f[n][]);

     return ;

 }

贪心的思想：每次取的花都应当在上升序列和下降序列的转折点上，加上首尾的花。

bzoj 1260: [CQOI2007] 涂色paint

 /*

 区间dp，f[i][j]表示区间i到j的答案。

 转移时枚举中间点即可。

 但是此题不同于一般dp之处在于，可以首先覆盖一部分，然后在覆盖这一部分其他的地方。

 这样或许是可以节省次数的。

 AAABA 例如对于这样的例子，直接合并找中间点是无法做到最优的，3步。

 而首先覆盖[1,5]，然后覆盖[4,4]只需要两步。 

 所以转移时应该特判，可以在很早时，已经可以顺便把这个点的情况。

 */

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 const int N = ;

 int f[N][N];

 char s[N];

 int main() {

     scanf("%s",s+);

     int n = strlen(s+);

     memset(f,0x3f,sizeof(f));

     for (int i=; i<=n; ++i) f[i][i] = ;

     for (int k=; k<=n; ++k) {

         for (int i=; (i+k-)<=n; ++i) {

             int j = i + k - ;

             if (s[i]==s[i+]) f[i][j] = f[i+][j];

             else if (s[j-]==s[j]) f[i][j] = f[i][j-];

             else if (s[i]==s[j]) f[i][j] = std::min(f[i][j-],f[i+][j]);

             else {

                 for (int m=i; m<j; ++m)

                     f[i][j] = std::min(f[i][j],f[i][m]+f[m+][j]);

             }

         }

     }

     std::cout<<f[][n];

     return ;

 }

bzoj 4247 挂饰

 /*

 考虑状态的表示f[i][j]表示到第i个物品，剩余j个挂钩，最大的价值。

 然后发现j无法转移，因为挂饰的顺序可以交换，可以在后面拿一个挂钩很多的，然后在前面选一些挂钩较少的。

 那么当前j是负数也无所谓了，只要后面有一个挂钩很多的，把前面的负数补上就可以了。 

 如何处理，

 1.允许负数，f[i][j]，j可以是负数。 （没写）

 2.改变枚举顺序，从挂钩多的到挂钩少的枚举。（排序） 

 如果用“拉”的写法：f[i][j] <- f[i][j-a[i]+1] （+1，表示一个挂钩挂第i个物品）

 然后，j-a[i]+1可能小于0，那么我们只要让他从f[i-1][1]转移就好了，表示只有一个挂钩挂第i个物品。

 如果用“推”的写法：f[i][j] -> f[i+1][j+a[i]-1] ，j+a[i]-1>n的时候，强制为n即可，大于n的没有用。 

 */

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cctype>

 const int N = ;

 struct Node{

     int a,b;

     bool operator < (const Node &A) const {

         return a > A.a;

     }

 }d[N];

 int f[N][N];

 inline int read() {

     int x = ,f = ;char ch=getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-')f=-;

     for (; isdigit(ch); ch=getchar()) x=x*+ch-'';

     return x*f;

 }

 int main() {

     int n = read();

     for (int i=; i<=n; ++i)

         d[i].a = read(),d[i].b = read();

     std::sort(d+,d+n+);

     memset(f,-0x3f,sizeof(f));

     f[][] = ;

     for (int i=; i<=n; ++i)

         for (int j=; j<=n; ++j)

             f[i][j] = std::max(f[i-][j],f[i-][std::max(j-d[i].a,)+]+d[i].b);

     int ans = ;

     for (int i=; i<=n; ++i)

         ans = std::max(ans,f[n][i]);

     std::cout<<ans;

     return ;

 }

bzoj 1296 [SCOI2009]粉刷匠

 /*

 给n个木板，一共可以刷T次，每次将可以将一段连续的格子刷成0/1 ，求最多可以刷多大的面积。

 n个木板是相互不干涉的，（不能跨木板刷，刚开始以为给了一个矩阵，然后以为可以竖着刷。。。）

 所以对于每个木板求出刷了1,2,3...T次的最大价值。

 然后背包合并即可。

 f[i][j]表示到第i个格子，刷了j次的最大价值。

 dp[i]表示一共刷了i次的最大价值。

 */

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 using namespace std;

 int f[][],dp[],sum[];

 char s[];

 int main() {

     int n,m,t;

     cin >> n >> m >> t;

     for (int T=; T<=n; ++T) {

         scanf("%s",s+);

         for (int i=; i<=m; ++i) sum[i] = sum[i-] + (s[i]=='');

         for (int i=; i<=m; ++i) {

             for (int j=; j<=i; ++j) {

                 f[i][j] = ; // 到第i个位置，用了j次。

                 for (int k=; k<i; ++k) { // 到第k个位置，用了j-1次 ,k=0表示从头开始涂。

                     f[i][j] = max(f[i][j],f[k][j-]+max(sum[i]-sum[k],i-k-sum[i]+sum[k]));

                 }

             }

         }

         for (int i=t; i>=; --i) {

             for (int j=,lim=min(i,m); j<=lim; ++j)

                 dp[i] = max(dp[i],dp[i-j]+f[m][j]);

         }

     }

     int ans = ;

     for (int i=; i<=t; ++i) ans = max(ans,dp[i]);

     cout << ans;

     return ;

 }

bzoj 1025 [SCOI2009]游戏

 /*

 思路题。

 首先将置换编程循环节的形式，那么答案为lcm(L1,L2,L3...Lk)，Li为第i个循环节的长度。

 （理解：假设每个置换是一个环，那么为了让所有的环走回起点，那么走的长度就是所有环的长度的最小公倍数）

 那么就是求和为n的序列的最小公倍数的种数。

 构造一个答案（即构造最小公倍数），判断是否可行。

 设构造的最小公倍数为A=p1^a1 * p2^a2 * p3^a3...

 那么假设每个循环节为A1=p1^a1, A2=p2^a2, A3=p3^a3

 因为这些循环节（Ai）之间没有共同的质因子，所以它们的lcm就是乘起来。

 对于这些循环节长度，如果它们的和<=n那么说明对于最小公倍数x是可行的（其它的循环节补1）。 

 那么就是求有多少种(a1,a2,a3,...am),满足p1^a1+p2^a2+p3^a3+...+pm^am<=n

 备注：每一种(a1,a2,a3...am)对应得p1^a1+p2^2+p3^a3 都是不同的。 

 f[i][j]表示前i个质数，和为j的方案数。f[i][j] += f[i-1][j-k]  k=pri[i]^0,1,2,... 

 */

 #include<cstdio>

 #include<iostream>

 #define LL long long

 #define N 1010

 LL f[N][N];

 int pri[N],n,tot;

 bool nopri[N];

 void getpri() {

     for (int i=; i<=n; ++i) {

         if (!nopri[i]) pri[++tot] = i;

         for (int j=; j<=tot&&i*pri[j]<=n; ++j) {

             nopri[i*pri[j]] = true;

             if (i % pri[j] == ) break;

         }

     }

 }

 void solve() {

     f[][] = ;

     // f[i][j] 前i个质数，和为j的排数。

     for (int i=; i<=tot; ++i) {

         for (int j=; j<=n; ++j) {

             f[i][j] = f[i-][j]; // 第i个质数不用，（即0次方）

             for (int k=pri[i]; k<=j; k*=pri[i]) { // 第i个质数的1,2,3...次方

                 f[i][j] += f[i-][j-k];

             }

         }

     }

     LL ans = ;

     for (int i=; i<=n; ++i) ans += f[tot][i];

     std::cout << ans;

 }

 int main() {

     std::cin >> n;

     getpri();

     solve();

     return ;

 }

bzoj 1055 [HAOI2008]玩具取名

 /*

 给定W,I,N,G转换为两个字母的规则。

 W -> IN  ...

 求一个最终的字符串可以由哪个字符转移而来，可能有1,2,3,4个。

 开始是想的是树的做法（推回去），发现连边太多。。。

 区间dp，f[i][j][k]=0/1 区间[l,r]能否有字符k转移而来（k=W,I,N,G）

 枚举左右起点，中间点，枚举转移规则，转移。

 开始时想的是，把每一个字符可以转移到的两个字符记下来。枚举每个字符转移。即枚举f[i][j][k]，k也枚举出来。

 后来在网上发现更简单的写法，直接把所有转移的规则记录下来，枚举所有的转移规则即可。

 由于有先后的顺序（IN->W ,NI-!>W），所以所有转移规则枚举一次即可，不需要反过来在枚举一次。

 即f[i][j][z] <- f[i][k][x] & f[k+1][j][y]

 不需要 f[i][j][z] <- f[i][k][y] & f[k+1][j][x]，而且这样是不对的。

 */

 #include<cstdio>

 #include<cstring>

 #define N 210

 struct Str{

     int x,y,z;

 }g[N];

 bool f[N][N][];

 int c[],p[N];

 char s[N];

 int main() {

     p['W'] = ;p['I'] = ;p['N'] = ;p['G'] = ;

     scanf("%d%d%d%d",&c[],&c[],&c[],&c[]);

     int cnt = ;

     for (int i=; i<=; ++i) {

         for (int j=; j<=c[i]; ++j) {

             scanf("%s",s);

             g[++cnt].x = p[s[]]; g[cnt].y = p[s[]]; g[cnt].z = i;

         }

     }

     scanf("%s",s+);

     int n = strlen(s+);

     for (int i=; i<=n; ++i) f[i][i][p[s[i]]] = true;

     for (int len=; len<=n; ++len) {

         for (int r,l=; (r=l+len-)<=n; ++l) {

             for (int k=l; k<=r; ++k) {

                 for (int i=; i<=cnt; ++i) {

                     f[l][r][g[i].z] |= (f[l][k][g[i].x] & f[k+][r][g[i].y]); // &比&&快好多

                 }

             }

         }

     }

     bool flag = false;

     if (f[][n][]) printf("W"),flag = true;

     if (f[][n][]) printf("I"),flag = true;

     if (f[][n][]) printf("N"),flag = true;

     if (f[][n][]) printf("G"),flag = true;

     if (!flag) printf("The name is wrong!");

     return ;

 }

bzoj 1084 [SCOI2005]最大子矩阵

 /*

 n*2的方格，选出k个矩阵。

 m=1时，经典dp，O(nnk)。f[i][j]到底i个位置，选了j个矩阵。转移：不选i或者枚举转移点k。 

 m=2时，转移时维护三维 dp[i][j][k]，左边一列到第i行，右边一列到底j行，选了k个矩阵。

 转移：不选：可以从左边和右边转移。

       选：  在左边枚举转移点，在右边枚举转移点，i=j时，可以左右边一起枚举转移点。 

 注意：转移时，不管到什么位置，必须要更新选了0个的情况（等于0），初始时更新一下行为0的情况。代码36,54行。

 */

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cctype>

 using namespace std;

 const int N = ;

 int dp[N][N][],sum[N][];

 int f[N][],s[N];

 int n,m,K;

 inline int read() {

     int x = ,f = ;char ch=getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-')f=-;

     for (; isdigit(ch); ch=getchar()) x=x*+ch-'';

     return x*f;

 }

 void solve1() {

     for (int i=; i<=n; ++i) s[i] = s[i-] + read();

     memset(f,-0x3f,sizeof(f));

     f[][] = ;

     for (int i=; i<=n; ++i) { // 到第i个位置

         f[i][] = ;

         for (int j=; j<=K; ++j) { // 选了j个矩阵

             f[i][j] = f[i-][j]; // 不选i

             for (int k=; k<i; ++k) { // 选i，那么i在的矩阵（当前矩阵）为[k+1~i]行。

                 f[i][j] = max(f[i][j],f[k][j-]+s[i]-s[k]);

             }

         }

     }

     cout << f[n][K];

 }

 void solve2() {

     for (int i=; i<=n; ++i)

         for (int j=; j<=m; ++j)

             sum[i][j] = sum[i-][j] + read();

     memset(dp,-0x3f,sizeof(dp));

     dp[][][] = ;

     for (int i=; i<=n; ++i) dp[i][][] = dp[][i][] = ;

     for (int i=; i<=n; ++i) { // 左边一列

         for (int j=; j<=n; ++j) { // 右边一列

             dp[i][j][] = ;

             for (int k=; k<=K; ++k) { // 选了k个矩阵

                 dp[i][j][k] = max(dp[i-][j][k],dp[i][j-][k]); // 当前这个位置不选

                 for (int p=; p<i; ++p) // 选i，其构成的当前矩阵是左边一列[p+1~i]行

                     dp[i][j][k] = max(dp[i][j][k],dp[p][j][k-]+sum[i][]-sum[p][]);

                 for (int p=; p<j; ++p) // 当前矩阵是右边一列[p+1~i]行

                     dp[i][j][k] = max(dp[i][j][k],dp[i][p][k-]+sum[j][]-sum[p][]);

                 if (i==j) {

                     for (int p=; p<i; ++p) // 当前矩阵是左右两列的 [p+1~i]行

                         dp[i][j][k] = max(dp[i][j][k],dp[p][p][k-]+sum[i][]-sum[p][]+sum[j][]-sum[p][]);

                 }

             }

         }

     }

     cout << dp[n][n][K];

 }

 int main() {

     n = read(),m = read(),K = read();

     if (m==) solve1();

     else solve2();

     return ;

 }

 /*

 5 1 2

 -9 10 2 -1 3

 */

bzoj 1304 [CQOI2009]叶子的染色

 #include<cstdio>

 #include<iostream>

 #include<cctype>

 using namespace std;

 const int INF = 1e9;

 const int N = ;

 int head[N],nxt[N<<],to[N<<],dp[N][];

 int n,m,Enum;

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;

     for (; isdigit(ch); ch=getchar()) x=x*+ch-'';

     return x * f;

 }

 void add_edge(int u,int v) {

     ++Enum; to[Enum] = v; nxt[Enum] = head[u]; head[u] = Enum;

     ++Enum; to[Enum] = u; nxt[Enum] = head[v]; head[v] = Enum;

 }

 void DP(int u,int fa) {

     if (u <= m) return ;

     dp[u][] = dp[u][] = ;

     for (int i=head[u]; i; i=nxt[i]) {

         int v = to[i];

         if (v==fa) continue;

         DP(v,u);

         dp[u][] += min(dp[v][]-,dp[v][]);

         dp[u][] += min(dp[v][]-,dp[v][]);

     }

 }

 int main () {

     n = read(),m = read();

     for (int i=; i<=m; ++i) {

         int c = read();

         dp[i][c] = ;dp[i][c^] = INF;

     }

     for (int i=; i<n; ++i) {

         int u = read(),v = read();

         add_edge(u,v);

     }

     DP(n,);

     cout << min(dp[n][],dp[n][]);

     return ;

 }

bzoj 1044 [HAOI2008]木棍分割

 /*

 先二分+贪心判断。

 然后dp

 f[i][j]到第i个数，分了j次的最大价值。

 f[i][j] = {sigma f[k][j-1] ,sum[i]-sum[k]<=Len}

 后面的“滑动窗口”处理。

 */

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 using namespace std;

 const int N = ;

 const int mod = ;

 int a[N],f[N][],q[N],sum[N],n,m;

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;

     for (; isdigit(ch); ch=getchar()) x=x*+ch-'';

     return x * f;

 }

 bool check(int x) {

     int cnt = ,sum = ; // zz的写成sum=1...

     for (int i=; i<=n; ++i) {

         sum += a[i];

         if (sum > x) {

             sum = a[i];

             cnt ++;

             if (cnt == m + ) return false;

         }

     }

     return true;

 }

 int main () {

     n = read(),m = read();

     int L = ,R = ,mid,ans;

     for (int i=; i<=n; ++i) {

         a[i] = read();

         L = max(L,a[i]),R += a[i];

         sum[i] = sum[i-] + a[i];

     }

     while (L <= R) {

         mid = (L + R) / ;

         if (check(mid)) ans = mid,R = mid - ;

         else L = mid + ;

     }

     cout << ans << ' ';

     int cur = ,Ans = ,tot;

     for (int i=; i<=n; ++i) f[i][cur] = sum[i]<=ans; // 划分了0次

     for (int j=; j<=m; ++j) {

         cur ^= ;

         tot = ,L = ;

         for (int i=; i<=n; ++i) {

             while (L < i && sum[i]-sum[L] > ans)

                 tot = (tot - f[L++][cur^] + mod) % mod;

             f[i][cur] = tot; // 到第i个位置，划分了j次。

             tot = (tot + f[i][cur^]) % mod;

         }

         Ans = (Ans + f[n][cur]) % mod;

     }

     cout << Ans;

     return ;

 }

bzoj 2431 [HAOI2009]逆序对数列

 /*

 求n个数(1,2,3...n)，有多少个的逆序对数为k的序列

 对于当前i个数j个逆序对的方案数为f[i][j]

 那么它可以递推到 f[i+1][j] ~ f[i+1][j+i]，即计算最后一个数放的位置

 复杂度n^3

 把上面的式子反过来，f[a][b]可以由 f[a-1][b-a+1] ~ f[a-1][b] 转移而来

 每次b+1，只有一个数增加一个数减去，所以记录一个类似滑动窗口的变量，O(1)转移即可。

 复杂度n^2

 bug一堆...

 */

 #include<cstdio>

 #include<iostream>

 using namespace std;

 int f[][];

 const int mod = ;

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;

     for (; isdigit(ch); ch=getchar()) x=x*+ch-'';

     return x * f;

 }

 int main () {

     int n,k;

     cin >> n >> k;

     f[][] = ;

     for (int i=; i<=n; ++i) {

         int sum = ;

         int limit = min((i*(i-))/,k);

         for (int j=; j<=limit; ++j) {

             sum = (sum + f[i-][j]) % mod;

             if (j - i >= ) sum = (sum - f[i-][j-i] + mod) % mod;

             f[i][j] = sum;

         }

     }

     cout << f[n][k];

     return ;

 }

bzoj 2423 [HAOI2010]最长公共子序列

 /*

 1、求两个字符串的最长公共子序列，n^2

 2、求最长的公共子序列有多少个，在第一问的基础上再加几次转移。

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 const int mod = ;

 int f[][N],g[][N];

 char a[N],b[N];

 int main () {

     scanf("%s%s",a+,b+);

     int A = strlen(a+) - ,B = strlen(b+) - ;

     for (int i=; i<=B; ++i) g[][i] = ;g[][] = ;

     int cur = ;

     for (int i=; i<=A; ++i) {

         cur ^= ;

         for (int j=; j<=B; ++j) {

             if (a[i] == b[j]) {

                 f[cur][j] = f[cur^][j-] + ;

                 g[cur][j] = g[cur^][j-];

                 if (f[cur][j] == f[cur][j-]) g[cur][j] = (g[cur][j] + g[cur][j-]) % mod;

                 if (f[cur][j] == f[cur^][j]) g[cur][j] = (g[cur][j] + g[cur^][j]) % mod;

             }

             else {

                 f[cur][j] = max(f[cur][j-],f[cur^][j]);

                 g[cur][j] = ;

                 if (f[cur][j] == f[cur][j-]) g[cur][j] = (g[cur][j] + g[cur][j-]) % mod;

                 if (f[cur][j] == f[cur^][j]) g[cur][j] = (g[cur][j] + g[cur^][j]) % mod;

                 if (f[cur][j] == f[cur^][j-]) g[cur][j] = (g[cur][j] - g[cur^][j-] + mod) % mod;//减去重复计算的

             }

         }

     }

     cout << f[cur][B] << "\n" << g[cur][B];

     return ;

 }

bzoj 3191 [JLOI2013]卡牌游戏

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 int a[N];

 double f[N][N]; // f[i][j]剩i个玩家，第j个人获胜的概率。 

 int main() {

     int n = read(),m = read();

     for (int i=; i<=m; ++i) a[i] = read();

     f[][] = 1.0;

     for (int i=; i<=n; ++i) { // 人数i

         for (int j=; j<=i; ++j) { // 获胜玩家j

             for (int k=; k<=m; ++k) { // 卡牌k

                 int t = a[k] % i; if (t==) t = i; // 出局玩家t

 //                if (t == j) continue;

                 f[i][j] += f[i-][(j-t+i)%i] / (1.0 * m); // t出局后，所有玩家编号-t，j就成了 j-t

             }

         }

     }

     for (int i=; i<n; ++i)

         printf("%.2lf%% ",f[n][i]*100.0);

     printf("%.2lf%%",f[n][n]*100.0);

         return ;

 }

baoj 1899 [Zjoi2004]Lunch 午餐

 /*

 两个窗口打饭，每个人有打饭时间与吃饭时间，将所有人分成两组分别到两个窗口，使总时间最小。

 f[i][j][k]到第i个人1号窗口等饭时间为j，2号窗口为k。空间开不下。

 sum[i]表示到i所有人的登饭时间之和。然后发现j+k=sum[i]，所以f[i][j]表示到第i人1号窗口等饭时间为j的总时间。

 分情况转移。

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ; 

 int f[N][N*N],sum[N];

 struct Node{

     int a,b;

     bool operator < (const Node &A) const {

         return b > A.b;

     }

 }T[N];

 int main() {

     int n = read();

     for (int i=; i<=n; ++i)

         T[i].a = read(),T[i].b = read();

     sort(T+,T+n+);

     for (int i=; i<=n; ++i) sum[i] = sum[i-] + T[i].a;

     memset(f,0x3f,sizeof(f));

     int ans = f[][];

     f[][] = ; 

     for (int i=; i<=n; ++i) {

         for (int j=; j<=sum[i-]; ++j) {

             // 第i个人在二号窗口，后面的取max为都吃完的时间。二号窗口的变动体现在，第一维从i-1到了i（即从i-1转移），sum[i]也就发生了变化。

             f[i][j] = min(f[i][j], max(f[i-][j], sum[i-]-j+T[i].a+T[i].b));

             // 在一号窗口

             f[i][j+T[i].a] = min(f[i][j+T[i].a], max(f[i-][j], j+T[i].a+T[i].b));

         }

     }

     for (int i=; i<=sum[n]; ++i) ans = min(ans,f[n][i]);

     cout << ans;

     return ;

 }

bzoj 1046 [HAOI2007]上升序列

 /*

 求出每个点往后的最长上升子序列，判断。

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 int a[],f[],g[];

 int find(int l,int r,int x) { // 单调递减-查找第一个大于x的数

     int ans = ;

     while (l <= r) {

         int mid = (l + r) >> ;

         if (g[mid] > x) ans = mid,l = mid + ;

         else r = mid - ;

     }

     return ans;

 }

 int main() {

     int n = read();

     for (int i=; i<=n; ++i) a[i] = read();

     int len = ;

     f[n] = ;g[len] = a[n];

     for (int i=n-; i>=; --i) {

         if (a[i] < g[len]) len++,g[len] = a[i],f[i] = len;

         else {

             int pos = find(,len,a[i]);

             g[pos+] = max(g[pos+],a[i]); // -写成了min。。。

             f[i] = pos + ;

         }

     }

     int m = read(),t,last;

     while (m--) {

         t = read();

         if (t > len) {puts("Impossible");continue;}

         last = ;

         for (int i=; ; ++i) {

             if (f[i] >= t && a[i] > a[last]) {

                 printf("%d ",a[i]);

                 last = i;

                 t --;

                 if (!t) break;

             }

         }

         puts("");

     }

     return ;

 }

bzoj 1820 [JSOI2010]Express Service 快递服务

 /*

 三个辆车是没有标号的，所以在dp是，顺序是无关的。

 f[i][a][b][c]表示到第i个位置，三辆车分别在a,b,c是的费用。

 空间太大。

 可以滚动掉第一维，但是空间还是太大。 

 然后发现a,b,c中其中一个必定是q[i](收件地点)。

 那么f[i][a][b]表示到第i个位置，三辆车分别在a,b,q[i]的最大价值。 

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 int g[N][N],a[N],f[][N][N];

 int main() {

     int n = read();

     for(int i=; i<=n; ++i)

         for (int j=; j<=n; ++j) g[i][j] = read();

     int tot = ;

     while (scanf("%d",&a[++tot]) != EOF) ;

     memset(f,0x3f,sizeof(f));

     int cur = ;

     f[cur][][] = g[][a[]];

     f[cur][][] = g[][a[]];

     f[cur][][] = g[][a[]];

     for (int i=; i<=tot; ++i) {

         cur ^= ;

         memset(f[cur],0x3f,sizeof(f[cur]));

         for (int j=; j<=n; ++j) {

             for (int k=j; k<=n; ++k) { // 从j开始！减小常数！

                  // 当前三辆车的位置为j,k,a[i]，所以从a[i-1]转移到a[i]

                 f[cur][j][k] = f[cur][k][j] = min(f[cur][j][k],f[cur^][j][k]+g[a[i-]][a[i]]);

                 // 当前三辆车的位置为a[i-1],k,a[i]，所以枚举一个j，从j转移到a[i]

                 f[cur][a[i-]][k] = f[cur][k][a[i-]] = min(f[cur][a[i-]][k],f[cur^][j][k]+g[j][a[i]]);

                 // 当前三辆车的位置为a[i-1],j,a[i]，所以枚举一个k，从k转移到a[i]

                 f[cur][a[i-]][j] = f[cur][j][a[i-]] = min(f[cur][a[i-]][j],f[cur^][j][k]+g[k][a[i]]);

             }

         }

     }

     int ans = 0x7fffffff;

     for (int i=; i<=n; ++i)

         for (int j=; j<=n; ++j)

             ans = min(ans,f[cur][i][j]);

     cout << ans;

     return ;

 }

bzoj 1996 [Hnoi2010]chorus 合唱队

 /*

 想出dp的状态表示！ 

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 const int mod = ;

 int f[N][N][],a[N]; 

 int main() {

     int n = read();

     for (int i=; i<=n; ++i)

         a[i] = read(),f[i][i][] = ;

     for (int i=n; i>=; --i) {

         for (int j=i+; j<=n; ++j) { // 区间i~j

             if (a[j] > a[i]) f[i][j][] += f[i][j-][];

             if (a[j] > a[j-]) f[i][j][] += f[i][j-][];

             if (a[i] < a[j]) f[i][j][] += f[i+][j][];

             if (a[i] < a[i+]) f[i][j][] += f[i+][j][];

             if (f[i][j][] > mod) f[i][j][] %= mod;

             if (f[i][j][] > mod) f[i][j][] %= mod;

         }

     }

     cout << (f[][n][] + f[][n][]) % mod;

     return ;

 }

bzoj 2660 [Beijing wc2012]最多的方案

 /*

 预处理出所有斐波那契数，然后从大到小选出一个方案。

 将斐波那契数按照01串排列，第i个为1表示第i个斐波那契数选。 

 1 2 3 5 8 13

 16 = 3 + 13         001001

 13 = 3 + 5 + 8      001110

 13 = 1 + 2 + 5 + 8  110110

 16 = 1 + 2 + 13     110001

 实质就是将一个高位的1的化为两个低位的1的过程，因为不能重复，所以每个位置只能有一个1，不能有多个。

 考虑一个1最多化为多少种方案：

 0000001 - 0000110 - 0011010 - 1101010

 000001 - 000110 - 011010

 每次只能 将最左边的一个1化为两个1，而右边的1是无法化下去的，所以可以化为的方案数为：1和上一个1之间的0的个数/2

 dp 模拟过程即可。dp[i][0/1]当前到第几位，是0还是1的方案数。 

 说明：比如0000110中的6号：

 1、6号要化简，那么先找5号，5-3,4

 2、此时再找4号，4号要化简，那么先找3号 3-1,2

 ...

 所以6号是无法化简的。

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 LL f[N],dp[N][],q[N];

 int main() {

     LL n;int tot = ;

     cin >> n;

     f[] = ,f[] = ;

     for (int i=; i<=; ++i) f[i] = f[i-] + f[i-];

     for (int i=; i>=; --i) {

         if (n >= f[i]) {

             q[++tot] = i;n -= f[i];

         }

     }

     sort(q+,q+tot+);

     dp[][] = ;dp[][] = (q[] - ) / ;

     for (int i=; i<=tot; ++i) {

         dp[i][] = dp[i-][] + dp[i-][];

         dp[i][] = dp[i-][]*((q[i]-q[i-])/) + dp[i-][]*((q[i]-q[i-]-)/); // 这里必须要把除以2括起来！

     }

     cout << dp[tot][] + dp[tot][];

     return ;

 }

bzoj 3612 [Heoi2014]平衡

 /*

 妙题！

 一个杠杆，左边长度为n，右边也是，之间也有一个点，每个点上一个橡皮，重量相同，问拿走k个有多少种方案是杠杆平衡。

 相当于整数划分，左边a个数构成c，右边选k-a个数，构成c。

 但是这里的整数划分不能取相同的数（每个位置上一个橡皮）。

 原整数划分方程 f[i][j]=f[i-1][j-1]+f[i-j][j]，分为增加一个1的 和 所有数都加1的转移。

 现在转移方程  f[i][j]=f[i-j][j-1]+f[i-j][j]，分为将所有数加1然后增加一个1的 和 所有数都加1的。 

 而且不能有>n的数。所以一旦有n+1了，就减去。

 当前为i>=n+1，假设之前的包含n+1的都减去了，i=(n+1)+(i-(n+1))

 就是说当前为i，有j个数，那么包含n+1的就是 和为(i-n-1)有j-1个数的个数，即f[i-n-][j-1] 

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 int f[][]; // 空间n*k 

 int main() {

     int Case = read();

     while (Case--) {

         int n = read(),k = read(),p = read();

         f[][] = ;

         int W = n * k; // 这里是最大的质量，其实是n+(n-1)+(n-2)+...共k个。

         for (int i=; i<=W; ++i) {

             for (int j=,lim=min(i,k); j<=lim; ++j) {

                 f[i][j] = (f[i-j][j-] + f[i-j][j]) % p;

                 if (i > n) f[i][j] = (f[i][j] - f[i-n-][j-] + p) % p;

             }

         }

         LL ans = ;

         for (int i=; i<=W; ++i) {

             for (int j=; j<=k; ++j) {

                 ans = (ans + 1ll * f[i][j] * f[i][k-j]) % p;

                 if (j < k) ans = (ans + 1ll * f[i][j] * f[i][k-j-]) % p; // 拿0号位置的物品

             }

         }

         cout << ans << "\n";

     }

     return ;

 }

bzoj 4321 queue2

 /*

 开始写了一个线性的递推，由i-1个时的方案数*(i-2)得到i的方案。发现不对。。。 

 想不出状态的表示，于是看题解。。。

 f[i][j][0/1]表示推到第i个数，其中有j对数是相差1的，其中i与i-1不相邻或相邻。

 为什么这样表示？ 

 开始想的是，当前状态，满足条件的个数，但是这没法转移。

 新加入一个数i，一个状态在i-1时不满足，而i插入到不满足的数对中间，使得没有相邻的了，满足了，所以只记录满足的情况是无法转移的，也要记下不满足的情况。

 所以正确的状态表示为记录当前有多少不满足的对数，即相差为一的。

 如果只用两维的话f[i][j]表示到第i个数，有j对的话。

 那么对于i-1和i-2挨着，i插入后和i-1挨着，但是插入到它们两个之间，此时是消了一对，加了一对，如果只用两维的话这种情况判不出来。 

 之后分情况讨论i放到哪个位置，进行转移。

 */

 #include<bits/stdc++.h>

 using namespace std;

 const int N = ;

 const int mod = ;

 long long f[N][N][];

 int main() {

     int n;cin >> n;

     f[][][] = ;

     for (int i=; i<=n; ++i) {

         for (int j=; j<=n; ++j) {

             f[i][j][] = (f[i-][j][] + f[i-][j-][] + f[i-][j-][] * ) % mod;

             f[i][j][] = (f[i-][j+][] * j + f[i-][j+][] * (j+)) % mod;

             f[i][j][] = (f[i][j][] + f[i-][j][] * (i-j-) + f[i-][j][] * (i-j-)) % mod;

         }

     }

     cout << f[n][][];

     return ;

 }

bzoj 1925 [Sdoi2010]地精部落

 /*

 https://www.cnblogs.com/ciao-sora/p/5988265.html

 粘个网址，以后再看。

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int N = ;

 int f[][N];

 int main() {

     int n,p;cin >> n >> p;

     if (n==) return !printf("");

     int cur = ;

     f[][] = ;

     for (int i=; i<=n; ++i) {

         cur ^= ;

         for (int j=; j<=n; ++j)

             f[cur][j] = (f[cur][j-] + f[cur^][i-j]) % p;

     }

     cout << (f[cur][n] * ) % p;

     return ;

 }

bzoj 1966 [Ahoi2005]VIRUS 病毒检测

 /*

 开始想的dp，第一个匹配到哪，第二个匹配到哪，能不能匹配上。

 然后发现复杂度有点大，看题解。。。就是这样。。。

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 bool f[N<<][N];

 char a[N<<],b[N]; // char a[N],b[N>>1]！

 int c[N<<]; // int c[N]！ 

 bool solve(int n,int m) {

     memset(f,false,sizeof(f));

     memset(c,0x3f,sizeof(c));

     f[][] = true;

     for (int i=; i<=n; ++i) {

         if (a[i] != '*') {

             for (int j=; j<=m; ++j) {

                 if (a[i] == '?' || a[i] == b[j]) {

                     f[i][j] |= f[i-][j-];

                     if (a[i-] == '*' && c[i-] < j) f[i][j] = ;

                 }

             }

         }

         else {

             if (i==) f[i][] = true;

             for (int j=; j<=m; ++j) {

                 f[i][j] = (f[i-][j] | f[i][j-]);

                 if (f[i][j]) c[i] = min(c[i],j);

             }

         }

     }

     if (f[n][m]) return false;

     return true;

 }

 int main() {

     scanf("%s",a+);int n = strlen(a+);

     int q = read(),ans = ;

     while (q--) {

         scanf("%s",b+);

         int m = strlen(b+);

         if (solve(n,m)) ans ++;

     }

     cout << ans;

     return ;

 }

bzoj 1237 [SCOI2008]配对

 /*

 如果没有不能相同配对的限制，那么排序后对应位置相减输出即可。

 题目中有这样一句话：保证所有 Ai各不相同，Bi也各不相同。

 开始时没读出来。。。

 首先还是排序。

 然后分情况看一下，如果A[i]!=B[i]那么直接计算答案即可。

 如果有连续一个相同的，那么它可以和上一个或者下一个交叉一下。

 如果有两个连续相同的，那么它们也可以交叉互换一下。

 如果有三个，可以进行三个的交叉互换，有三种交换的情况。

 如果有四个，那么可以拆成两个的。

 如果有五个，也可以拆。

 ...

 所以最多可以和前后2个位置的数交换。既保证满足条件，也保证是最优的。 

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const LL INF = 1e18;

 const int N = 1e5+;

 LL a[N],b[N],f[N];

 #define get(a,b) (a==b?INF:abs(a-b))

 int main() {

     int n = read();

     for (int i=; i<=n; ++i)

         a[i] = read(),b[i] = read();

     sort(a+,a+n+);

     sort(b+,b+n+);

     if (n ==  && a[] == b[]) return !printf("-1");

     f[] = get(a[],b[]);

     f[] = min(f[]+get(a[],b[]),get(a[],b[])+get(a[],b[]));

     for (int i=; i<=n; ++i) {

         f[i] = f[i-] + get(a[i],b[i]);

         f[i] = min(f[i],f[i-]+get(a[i-],b[i])+get(b[i-],a[i]));

         f[i] = min(f[i],f[i-]+get(a[i],b[i-])+get(a[i-],b[i])+get(a[i-],b[i-]));

         f[i] = min(f[i],f[i-]+get(a[i],b[i-])+get(a[i-],b[i-])+get(a[i-],b[i]));

         f[i] = min(f[i],f[i-]+get(a[i],b[i-])+get(a[i-],b[i-])+get(a[i-],b[i]));

     }

     cout << f[n];

     return ;

 }

bzoj 1560 [JSOI2009]火星藏宝图

 /*

 妙题！巧妙的优化！

 首先如果想到的是n^2的dp，建立一个拓扑图，在拓扑图上进行dp。

 发现如果a->b->c进行转移，一定不如a->c转移优，即(x+y)^2 = x^2 + y^2 + 2xy > x^2 + y^2

 所以每个点只会从和他临近的点转移，然后就不会了。。。

 这个临近具体是什么呢？

 考虑如何一个点会成为b这样的，可以确定每一列中，如果有一个点比b还要靠下，那么b就不会即系转换以，b可以转移到这个点，这个点在转移。

 那么可以维护每一列最靠下的点是哪个，对于一个点，直接从这些点中转移即可。

 其实这些点有些也是可以被替代的。

 时间复杂度O(nm) 

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = 2e5+;

 const int M = 1e3+;

 struct Node{

     int x,y,w;

     bool operator < (const Node &A) const {

         if (x == A.x) return y < A.y;

         return x < A.x;

     }

 }A[N];

 int f[M],pos[M];

 int main() {

     int n = read(),m = read();

     for (int i=; i<=n; ++i) {

         A[i].x = read(),A[i].y = read(),A[i].w = read();

     }

     sort(A+,A+n+);

     f[] = ;pos[] = ;

     for (int i=; i<=n; ++i) {

         int t = -0x7fffffff;

         for (int j=; j<=A[i].y; ++j) {

             if (pos[j])

                 t = max(t,f[j]-(A[i].x-pos[j])*(A[i].x-pos[j])-(A[i].y-j)*(A[i].y-j));

         }

         f[A[i].y] = t + A[i].w;

         pos[A[i].y] = A[i].x;

     }

     cout << f[m];

     return ;

 }

bzoj 3174 [Tjoi2013]拯救小矮人

 /*

 贪心+dp

 贪心的思想，a+b比较小的先走，那么逃跑的人是排序后的一段a+b的上升序列，所以首先按照a+b排序。

 贪心可以确定取的顺序是最优的，但是还要确定最多能走掉多少个

 接下来要dp：令f[i]表示走完i个矮人之后还能取到的最大高度

 这样贪心的作用就出来了：按照贪心完的顺序取走矮人，可以保证最优。

 一开始初始化f[0]表示没有矮人走掉，f[0]=Σa[i]。

 然后就是枚举取到第i个矮人，可以用它来更新f[j]的情况是f[j]+hi.b>=H。

 这样就可以算出最大值了

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 struct Node{

     int a,b;

     bool operator < (const Node &A) const {

         return (a + b) < (A.a + A.b);

     }

 }h[N];

 int f[N];

 int main() {

     int n = read(),sum = ;

     for (int i=; i<=n; ++i)

         h[i].a = read(),h[i].b = read(),sum += h[i].a;

     sort(h+,h+n+);

     memset(f,-,sizeof(f));

     f[] = sum;

     int H = read(),ans = ;

     for (int i=; i<=n; ++i) {

         for (int j=ans; j>=; --j) {

             if (f[j] + h[i].b >= H) f[j+] = max(f[j+],f[j]-h[i].a);

         }

         if (f[ans+] >= ) ans++;

     }

     cout << ans;

     return ;

 }

bzoj 1855 [Scoi2010]股票交易

 /*

 f[i][j]表示到第i天，有j股的最大价值。

 朴素n^3，

 枚举天，枚举股票，枚举买了多少股票。

 f[i][j] = max(f[i-1][j],f[i-w-1][j-k]-ak))

 转化枚举上一天有多少股票

 f[i][j] = max(f[i-1][j],f[i-w-1][k]-a(j-k))

 f[i][j] = max(f[i-1][j],f[i-w-1][k]+ak-aj)

 f[i-w-1][k]+ak 用单调队列优化。

 https://www.cnblogs.com/qt666/p/7425571.html

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 int f[N][N],q[N],L,R;

 int main() {

     memset(f,-0x3f,sizeof(f));

     int n = read(),m = read(),w = read();

     for (int i=; i<=n; ++i) {

         int a = read(),b = read(),s = read(),t = read();

         for (int j=; j<=s; ++j) f[i][j] = -a*j; // 买入

         for (int j=; j<=m; ++j) f[i][j] = max(f[i][j],f[i-][j]); // 卖出

         if (i <= w) continue;

         L = ,R = ;

         for (int j=; j<=m; ++j) { // 买入

             while (L <= R && q[L] < j - s) L++; // 最多买s股，保证买的合法

             while (L <= R && f[i-w-][q[R]]+q[R]*a <= f[i-w-][j]+j*a) R--; // 每次取大的，保证转移的点最优

             q[++R] = j;

             if (L <= R) f[i][j] = max(f[i][j],f[i-w-][q[L]]+q[L]*a-j*a);

         }

         L = ,R = ;

         for (int j=m; j>=; --j) { // 卖出

             while (L <= R && q[L] > j + t) L ++; // --j + b

             while (L <= R && f[i-w-][q[R]]+q[R]*b <= f[i-w-][j]+j*b) R--;

             q[++R] = j;

             if (L <= R) f[i][j] = max(f[i][j],f[i-w-][q[L]]+q[L]*b-j*b);

         }

     }

     int ans = ;

     for (int i=; i<=m; ++i) ans = max(ans,f[n][i]);

     cout << ans;

     return ;

 }

bzoj 2424 [HAOI2010]订货

 /*

 推出状态的表示和转移方程。

 f[i][j]表示到第i天，库存量为j（这个库存量表示今天已经卖完了剩下的）的花费。

 枚举上一天的库存量。

     f[i][j] = f[i-1][k] + k*m + (j+u-k)*d

     f[i][j] = f[i-1][k] + (m-d)*k + (j+u)*d;

 发现对于i从1~i中取最小的，

 对于i+1从1~i+1中取最小的，

 那么其中1~i的是重复的，所以记一个变量，每次取min即可。

 与单调队列转移不同的是：

     每个点的转移区间是递增的。

     i:   1~10

     i+1: 3~12

     i+2: 7~15

     这样重复的计算的是两个区间重叠的部分，前面也有不满足的。

     所以每次需要在前面弹出一些不满足的，在后面弹出一些较大的（默认从小的转移）。

     然后加入当前的。 

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 #define Rep(i,a,b) for (int i = (a); i <= b; ++ i)

 const int N = ;

 const int M = ;

 int f[N][M],U[N],d[N];

 int main() {

     int n = read(),m = read(),S = read();

     Rep (i,,n) U[i] = read();

     Rep (i,,n) d[i] = read();

     memset(f,0x3f,sizeof(f));

     f[][] = ;

     Rep (i,,n) {

         int res = 1e9,k = ;

         Rep (j,,S) {

             while (k <= min(j+U[i],S)) {

                 res = min(res, f[i-][k] + (m - d[i]) * k); k++;

             }

             f[i][j] = res + (j + U[i]) * d[i];

         }

     }

     cout << f[n][];

     return ;

 }

bzoj 1063 [Noi2008]道路设计

 /*

 神奇树形dp。

 如果树是一条链，那么不便利程度的最小值0，二叉树也是0

 所以只有三叉树及以上才会有不便利程度。

 当然是三叉树的不便利程度最大（因为相同的节点，三叉树的深度更大）。

 然后计算出三叉树的不便利程度最大是10；

 而且每个点最多被一条铁路覆盖，所以每个根节点最多向儿子连两条边，（合为一条铁路）

 于是状态可以表示为 f[N][j][k=0/1/2] 第i个节点，最大的不便利程度为j，向儿子连了0/1/2条边

 分情况转移。 

 明白状态是怎么来的，为什么这样表示状态！

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 int head[N],nxt[N<<],to[N<<],Enum;

 LL f[N][][],mod; // 第i个节点，最大的不便利程度为j，向儿子连了0/1/2条边 

 void add_edge(int u,int v) {

     ++Enum; to[Enum] = v; nxt[Enum] = head[u]; head[u] = Enum;

 }

 LL get(LL t) {

     if (!t) return ;

     return t % mod ? t % mod : mod; // --

 }

 void dfs(int u,int fa) {

     for (int i=; i<=; ++i) f[u][i][] = ;

     for (int i=head[u]; i; i=nxt[i]) {

         int v = to[i];

         if (v == fa) continue;

         dfs(v,u);

         for (int j=; j<=; ++j) {

             LL f0 = !j ?  : f[v][j-][] + f[v][j-][] + f[v][j-][];  // 不向这个儿子连边

             LL f1 = f[v][j][] + f[v][j][]; // 向这个儿子连边

             LL tmp = f[u][j][] * f0 + f[u][j][] * f1; f[u][j][] = get(tmp); //原来2条*现在0条，原来1条*现在1条

             tmp = f[u][j][] * f0 + f[u][j][] * f1; f[u][j][] = get(tmp); //原来1条*现在0条，原来1条*现在1条

             tmp = f[u][j][] * f0; f[u][j][] = get(tmp);//原来0条*现在0条

         }

     }

 }

 int main() {

     int n = read(),m = read(); mod = read();

     for (int i=; i<=m; ++i) {

         int u = read(),v = read();

         add_edge(u,v);add_edge(v,u);

     }

     if (m != n - ) {

         puts("-1\n-1");return ;  // --

     }

     dfs(,);

     LL ans;

     for (int i=; i<=; ++i) {

         if (ans = f[][i][] + f[][i][] + f[][i][]) {

             printf("%d\n%d",i,ans%mod);

             break;

         }

     }

     return ;

 }

bzoj 1812 [Ioi2005]riv

 /*

 树形背包，然后就不会了。。

 首先转化成二叉树。没想到。

 f[i][j][k] 表示以i为根的子树内，有j个伐木场，距离i最近的伐木场为k（k是i的祖先）

 */

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 const int INF = 1e9;

 int head[N],nxt[N<<],to[N<<],len[N<<],Enum,dis[N];

 int f[N][N][N],w[N],tr[N],ls[N],rs[N];

 void add_edge(int u,int v,int w) {

     ++Enum; to[Enum] = v; len[Enum] = w; nxt[Enum] = head[u]; head[u] = Enum;

 }

 void dfs(int u,int fa) {

     for (int i=head[u]; i; i=nxt[i]) {

         int v = to[i];

         if (v == fa) continue;

         dis[v] = dis[u] + len[i];

         dfs(v,u);

     }

 }

 int dp(int i,int j,int k) {

     if (f[i][j][k] != -) return f[i][j][k];

     f[i][j][k] = INF;

     int res = ;

     for (int t=; t<=j; ++t) {

         res = ;

         if (ls[i]) res += dp(ls[i],t,k); // i不建伐木场

         if (rs[i]) res += dp(rs[i],j-t,k); // i不建伐木场

         f[i][j][k] = min(f[i][j][k], res+(dis[i]-dis[k])*w[i]); // 加上i到伐木场的花费。

         if (t < j) {

             res = ;

             if (ls[i]) res += dp(ls[i],t,i); // 建伐木场

             if (rs[i]) res += dp(rs[i],j-t-,k); // 除了左儿子，其他的都是i的兄弟节点，i建伐木场对其没有影响

             f[i][j][k] = min(f[i][j][k],res);

         }

     }

     return f[i][j][k];

 }

 int main() {

     int n = read(),m = read();

     memset(tr,-,sizeof(tr));

     for (int i=; i<=n; ++i) {

         w[i] = read();

         int x = read(), len = read();

         if (tr[x] == -) ls[x] = i,tr[x] = i;

         else rs[tr[x]] = i,tr[x] = i;

         add_edge(x,i,len);

     }

     dfs(,);

     memset(f,-,sizeof(f));

     printf("%d\n",dp(,m,));

     return ;

 }

COGS 2240 [HZOI 2016]架设电话线路

 /*

 首先可以O(n*max(h[i])^2)即O(n*100*100)的dp

 f[i][j]表示到i，高度为j，然后从i-1转移，转移O(100*100)

 考虑如何优化转移。

 对于f[i][j]，考虑f[i-1][k]，假设k<j

 那么f[i][j] = f[i-1][k] + c(j - k) + (j - h[i]) ^ 2

 f[i][j] = f[i-1][k]- ck + cj + (j - h[i]) ^ 2

 设设为wij = cj + (j - h[i]) ^ 2

 f[i][j] = f[i-1][k]- ck + wij

 wij只与i和j有关系，对于f[i][j]是固定的，所以现在只需要找到一个k，使得f[i-1][k]-ck最小就好了。

 同理对于k>j的也要做一遍。

 */

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cctype>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x = , f = ; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -;

     for (; isdigit(ch); ch=getchar()) x = x *  + ch - ''; return x * f;

 }

 int f[][], h[];

 int main() {

     freopen("phonewire.in","r",stdin);freopen("phonewire.out","w",stdout);

     int n = read(), c = read();

     for (int i=; i<=n; ++i) h[i] = read();

     int cur = ;

     for (int i=h[]; i<=; ++i) f[cur][i] = (i - h[]) * (i - h[]);

     for (int i=; i<=n; ++i) {

         cur ^= ;

         memset(f[cur], 0x3f, sizeof(f[cur]));

         for (int res=1e9,j=; j<=; ++j) {

             if (j >= h[i - ]) res = min(res, f[cur ^ ][j] - c * j);

             if (j >= h[i]) f[cur][j] = min(f[cur][j], res + c * j + (j - h[i]) * (j - h[i]));

         }

         for (int res=1e9,j=; j>=; --j) {

             if (j >= h[i - ]) res = min(res, f[cur ^ ][j] + c * j);

             if (j >= h[i]) f[cur][j] = min(f[cur][j], res - c * j + (j - h[i]) * (j - h[i]));

         }

     }

     int ans = 1e9;

     for (int i=; i<=; ++i) ans = min(ans, f[cur][i]);

     cout << ans;

     return ;

 }

－－－－－－－－

最新文章

  1. 在Solr中配置和使用ansj分词
  2. 关于对inputstream流的复制
  3. MyEclipse护眼模式、字体大小的调整
  4. poj 2503 Babelfish (查找 map)
  5. Chomp!游戏 （组合游戏Combinatorial Games）
  6. datetimepicker 初始化只显示年
  7. 利用Python读取Matlab的Mat文件内容
  8. Android学习总结——实时显示系统时间
  9. c# 数据导出成excel 方法总结 见标红部分
  10. Visual Studio warning MSB3270:There was a mismatch between the processor architecture of the project being built &quot;MSIL&quot;
  11. loopj.com android-async-http
  12. MyBatis《1》
  13. springboot整合mybatis（使用MyBatis Generator)
  14. SQL 快速生成不重复的卡号
  15. Centos下，Docker部署Yapi接口管理平台（详细得令人发指）
  16. ionic3安卓版release发布
  17. 斯坦福大学公开课机器学习：Neural network-model representation（神经网络模型及神经单元的理解）
  18. 【Python】requests.post请求注册实例
  19. 修改SQL Server数据库表的创建时间最简单最直接有效的方法
  20. vscode用法

热门文章

  1. 7天学完Java基础之0/7
  2. 利用Cookie保存用户身份信息实现免登录
  3. win10+asp+access 父路径开启无效
  4. ubuntu安装robo3t
  5. Python开发环境Wing IDE设置Python路径详解
  6. TX Text Control X10独家揭秘之使用对象作为数据源
  7. 如何在SAP Server Side JavaScript里消费destination
  8. cesium加载shp格式数据
  9. Json的本地写入和读取，也可以方便在开发中数据的调试
  10. opencv　approxPolyDP使用