dp专练

dp练习。

codevs 1048 石子归并 

区间dp

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>

using namespace std;

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

inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; ch<'0'||ch>'9'; ch = getchar()) if (ch=='-') f = -1;
    for (; ch>='0'&&ch<='9'; ch = getchar()) x = x * 10 + ch - '0';
    return x * f;
}

int main() {
    memset(f,0x3f,sizeof(f));
    int n = read();
    for (int i=1; i<=n; ++i) w[i] = read();
    for (int i=1; i<=n; ++i) sum[i] = sum[i-1] + w[i];
    for (int i=1; i<=n; ++i) f[i][i] = 0;
    for (int i=n; i>=1; --i) // 枚举顺序：确保下次计算的状态中需要用到的状态已经计算出了。
        for (int j=i+1; j<=n; ++j) 
            for (int k=i; k<j; ++k) 
                f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
    printf("%d
",f[1][n]);
    return 0;
}

codevs  1090 加分二叉树

区间dp

#include<cstdio>

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

inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; ch<'0'||ch>'9'; ch = getchar()) if (ch=='-') f = -1;
    for (; ch>='0'&&ch<='9'; ch = getchar()) x = x * 10 + ch - '0';
    return x * f;
}
void dfs(int l,int r) {
    if (l > r) return ;
    printf("%d ",rt[l][r]);
    dfs(l,rt[l][r]-1);
    dfs(rt[l][r]+1,r);
}
int main() {
    int n = read();
    for (int i=1; i<=n; ++i) w[i] = read();
    for (int i=1; i<=n; ++i)
            f[i][i] = w[i],rt[i][i] = i;
    for (int i=n; i>=1; --i) 
        for (int j=i+1; j<=n; ++j) // 中序遍历i~j的子树
            for (int t,k=i; k<=j; ++k) { // 枚举根为k
                if (k==i) t = f[k+1][j] + w[k];
                else if (k==j) t = f[i][k-1] + w[k];
                else t = f[i][k-1]*f[k+1][j]+w[k];
                if (t > f[i][j]) f[i][j] = t,rt[i][j] = k;
            }
    printf("%d",f[1][n]);
    puts("");
    dfs(1,n);
    return 0;
}

openjudge 1768 最大子矩阵

n^3求最大子矩阵

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

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

int main () {
    int n;
    scanf("%d",&n);
    for (int i=1; i<=n; ++i) 
        for (int j=1; j<=n; ++j) 
            scanf("%d",&a[i][j]);
    for (int j=1; j<=n; ++j) // lie 
        for (int i=1; i<=n; ++i) // hang
            s[j][i] = s[j][i-1] + a[i][j];
    int ans = 0;
    for (int i=1; i<=n; ++i) { // hang1
        for (int j=i; j<=n; ++j) { // hang2
            memset(f,0,sizeof(f));
            for (int k=1; k<=n; ++k) { // lie
                f[k] = max(0,f[k-1])+s[k][j]-s[k][i-1];
                ans = max(ans,f[k]);
            }
        }
    }
    printf("%d",ans);
    return 0;
}

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[100100],f[100100];

int main () {
    int T,n;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        for (int i=1; i<=n; ++i) scanf("%d",&a[i]);
        if (n==1) {printf("%d
",a[1]);continue;}
        if (n==2) {printf("%d
",max(a[1],a[2]));continue;}
        
        memset(f,0,sizeof(f));
        int mx = a[1];
        f[1] = a[1];
        f[2] = max(a[1],a[2]);
        for (int i=3; i<=n; ++i) {
            f[i] = mx + a[i];
            mx = max(f[i-1],mx);
        }
        int ans = -1;
        for (int i=1; i<=n; ++i) 
            ans = max(ans,f[i]);
        printf("%d
",ans);
    }
    return 0;
}

openjudge 8464 股票买卖

//读懂题目，只有两次买卖 
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>

using namespace std;

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

int main () {
    int T,n;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        for (int i=1; i<=n; ++i) scanf("%d",&a[i]);
        memset(f1,0,sizeof(f1));
        memset(f2,0,sizeof(f2));
        int mn = a[1];f1[1] = 0;
        for (int i=2; i<=n; ++i) {
            f1[i] = a[i] - mn;
            f1[i] = max(f1[i],f1[i-1]);
            mn = min(a[i],mn);
        }
        int mx = a[n];f2[n] = 0;
        for (int i=n-1; i>=1; --i) {
            f2[i] = mx - a[i];
            f2[i] = max(f2[i],f2[i+1]);
            mx = max(a[i],mx);
        }
        int ans = -1;
        for (int i=2; i<n; ++i) {
            ans = max(ans,f1[i-1]+f2[i]);
        }
        printf("%d
",ans);
    }
    return 0;
}

openjudge 9268 酒鬼

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>

using namespace std;

int a[1010],f[1010];

int main () {
    int n;
    scanf("%d",&n);
    for (int i=1; i<=n; ++i) 
        scanf("%d",&a[i]);
    f[1] = a[1];
    f[2] = a[1] + a[2];
    //当前酒可以不喝，可以喝一瓶，连续两瓶
    for (int i=3; i<=n; ++i) 
        f[i] = max(f[i-1],max(f[i-2]+a[i],f[i-3]+a[i-1]+a[i]));
    printf("%d",f[n]);
    return 0;
}

openjudge 7614 最低通行费

//时间是2n-1，所以只能往右或往下走
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>

using namespace std;

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

int main () {
    int n;
    scanf("%d",&n);
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j) 
            scanf("%d",&a[i][j]);
    memset(f,0x3f,sizeof(f));
    f[1][0] = f[0][1] = 0;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=n; ++j) {
            int shang = f[i-1][j],zuo = f[i][j-1],aa = a[i][j];
            f[i][j] = min(f[i-1][j],f[i][j-1]) + a[i][j];
            int ff = f[i][j];
            ff = f[i][j];
        }
    }
    printf("%d",f[n][n]);
    return 0;
}

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[1010][1010];
int a[1010];
 
inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
    for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
    return x * f;
}
 
int main() {
    int n = read(),s = read(),t = read();
    for (int i=1; i<=n; ++i) a[i] = read();
    memset(f,false,sizeof(f));
    f[0][s] = true;
    for (int i=1; i<=n; ++i) {
        for (int j=0; j<=t; ++j) {
            if (j-a[i] >= 0) f[i][j] |= f[i-1][j-a[i]];
            if (j+a[i] <= t) f[i][j] |= f[i-1][j+a[i]];
        }
    }
    int ans=-1;
    for (int i=1; i<=t; ++i) 
        if (f[n][i]) ans = i;
    cout << ans;
    return 0;
}

luogu 1052 过河

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>

using namespace std;

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

inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
    for (; isdigit(ch); ch=getchar()) x = x*10+ch-'0';
    return x * f;
}

int main() {
    int n = read();
    int s = read(),t = read(),m = read();
    for (int i=1; i<=m; ++i) a[i] = read();
    sort(a+1,a+m+1);
    for (int i=1; i<=m; ++i) 
        d[i] = (a[i]-a[i-1])%2520;
    for (int i=1; i<=m; ++i) {
        a[i] = a[i-1] + d[i];
        v[a[i]] = 1;
    }
    int L = a[m];
    memset(f,0x3f,sizeof(f));
    f[0] = 0;
    for (int i=1; i<=L+t; ++i) {
        for (int j=s; j<=t; ++j) {
            if (i-j>=0) 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 0;
}

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[100100],f[50];
 
inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
    for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
    return x * f;
}
 
int main() {
    int n = read();
    for (int i=1; i<=n; ++i) b[i] = read();
    for (int i=1; i<=n; ++i) {
        int mx = 0;
        for (int j=0; j<=30; ++j) 
            if (b[i] & (1<<j)) mx = max(mx,f[j]);
        for (int j=0; j<=30; ++j) 
            if (b[i] & (1<<j)) f[j] = max(f[j],mx+1);
    }
    int ans = 0;
    for (int i=0; i<=30; ++i) ans = max(ans,f[i]);
    cout << ans;
    return 0;
}

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 = 110;
int n;
double f[N][N],k,c;
int sum[N];

double dfs(int l,int r) {
    if (l > r) return 0;
    if (f[l][r] != -1) return f[l][r];
    double &ans = f[l][r];
    ans = 1e18;
    for (int i=l; i<=r; ++i) 
        ans = min(ans,dfs(l,i-1)+dfs(i+1,r)+(1.0*c*(sum[i]-sum[i-1]))/(1.0*sum[n]));
    ans += (1.0*k*(sum[r]-sum[l-1]))/(1.0*sum[n]);
    return ans;
}
int main() {
    scanf("%d%lf%lf",&n,&k,&c);
    for (int a,i=1; i<=n; ++i) {
        scanf("%d",&sum[i]);sum[i] += sum[i-1];
    }
    for (int i=1; i<=35; ++i) 
        for (int j=1; j<=35; ++j) 
            f[i][j] = -1;
    printf("%.3lf",dfs(1,n));
    return 0;
}

luogu P1970 花匠

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>

using namespace std;

const int N = 100100;
int a[N],f[N][2];

inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
    for (; isdigit(ch); ch=getchar()) x = x*10+ch-'0';
    return x * f;
}

int main() {
    int n = read();
    for (int i=1; i<=n; ++i) a[i] = read();
    f[1][0] = f[1][1] = 1;
    for (int i=2; i<=n; ++i) {
        if (a[i] > a[i-1]) {
            f[i][1] = f[i-1][0] + 1;
            f[i][0] = f[i-1][0];
        } else if (a[i-1] > a[i]) {
            f[i][0] = f[i-1][1] + 1;
            f[i][1] = f[i-1][1];
        } else {
            f[i][0] = f[i-1][0];
            f[i][1] = f[i-1][1];
        }
    }
    cout << max(f[n][0],f[n][1]);    
    return 0;
}

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

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 = 55;
int f[N][N];
char s[N];

int main() {
    scanf("%s",s+1);
    int n = strlen(s+1);
    memset(f,0x3f,sizeof(f));
    for (int i=1; i<=n; ++i) f[i][i] = 1;
    for (int k=2; k<=n; ++k) {
        for (int i=1; (i+k-1)<=n; ++i) {
            int j = i + k - 1;
            if (s[i]==s[i+1]) f[i][j] = f[i+1][j];
            else if (s[j-1]==s[j]) f[i][j] = f[i][j-1];
            else if (s[i]==s[j]) f[i][j] = std::min(f[i][j-1],f[i+1][j]);
            else {
                for (int m=i; m<j; ++m) 
                    f[i][j] = std::min(f[i][j],f[i][m]+f[m+1][j]);
            }
        }
    }
    std::cout<<f[1][n];
    return 0;
}

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 = 2010;

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 = 0,f = 1;char ch=getchar();
    for (; !isdigit(ch); ch=getchar()) if(ch=='-')f=-1;
    for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
int main() {
    int n = read();
    for (int i=1; i<=n; ++i) 
        d[i].a = read(),d[i].b = read();
    std::sort(d+1,d+n+1);
    memset(f,-0x3f,sizeof(f));
    f[0][1] = 0;
    for (int i=1; i<=n; ++i) 
        for (int j=0; j<=n; ++j) 
            f[i][j] = std::max(f[i-1][j],f[i-1][std::max(j-d[i].a,0)+1]+d[i].b);
    int ans = 0;
    for (int i=0; i<=n; ++i) 
        ans = std::max(ans,f[n][i]);
    std::cout<<ans;
    return 0;
}

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[55][55],dp[2500],sum[55];
char s[55];


int main() {
    int n,m,t;
    cin >> n >> m >> t;
    for (int T=1; T<=n; ++T) {
        scanf("%s",s+1);
        for (int i=1; i<=m; ++i) sum[i] = sum[i-1] + (s[i]=='1');
                
        for (int i=1; i<=m; ++i) {
            for (int j=1; j<=i; ++j) {
                f[i][j] = 1; // 到第i个位置，用了j次。 
                for (int k=0; k<i; ++k) { // 到第k个位置，用了j-1次 ,k=0表示从头开始涂。 
                    f[i][j] = max(f[i][j],f[k][j-1]+max(sum[i]-sum[k],i-k-sum[i]+sum[k])); 
                }
            }
        }
        
        for (int i=t; i>=0; --i) {
            for (int j=1,lim=min(i,m); j<=lim; ++j) 
                dp[i] = max(dp[i],dp[i-j]+f[m][j]);
        }
    }
    
    int ans = 0;
    for (int i=1; i<=t; ++i) ans = max(ans,dp[i]);
    cout << ans;
    
    return 0;
}

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=2; i<=n; ++i) {
        if (!nopri[i]) pri[++tot] = i;
        for (int j=1; j<=tot&&i*pri[j]<=n; ++j) { 
            nopri[i*pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }
}
void solve() {
    f[0][0] = 1; 
    // f[i][j] 前i个质数，和为j的排数。
    for (int i=1; i<=tot; ++i) {
        for (int j=0; j<=n; ++j) {
            f[i][j] = f[i-1][j]; // 第i个质数不用，（即0次方） 
            for (int k=pri[i]; k<=j; k*=pri[i]) { // 第i个质数的1,2,3...次方 
                f[i][j] += f[i-1][j-k];
            }
        }
    }
    LL ans = 0;
    for (int i=0; i<=n; ++i) ans += f[tot][i];
    std::cout << ans;
}
int main() {
    std::cin >> n;
    getpri();
    solve();
    return 0;
}

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][5];
int c[5],p[N];
char s[N];

int main() {
    p['W'] = 1;p['I'] = 2;p['N'] = 3;p['G'] = 4;
    scanf("%d%d%d%d",&c[1],&c[2],&c[3],&c[4]);
    int cnt = 0;
    for (int i=1; i<=4; ++i) {
        for (int j=1; j<=c[i]; ++j) {
            scanf("%s",s);
            g[++cnt].x = p[s[0]]; g[cnt].y = p[s[1]]; g[cnt].z = i;
        }
    }
    scanf("%s",s+1);
    int n = strlen(s+1);
    for (int i=1; i<=n; ++i) f[i][i][p[s[i]]] = true;
    
    for (int len=2; len<=n; ++len) {
        for (int r,l=1; (r=l+len-1)<=n; ++l) {
            for (int k=l; k<=r; ++k) {
                for (int i=1; i<=cnt; ++i) {
                    f[l][r][g[i].z] |= (f[l][k][g[i].x] & f[k+1][r][g[i].y]); // &比&&快好多 
                }
            }
        }
    }
    
    bool flag = false;
    if (f[1][n][1]) printf("W"),flag = true;
    if (f[1][n][2]) printf("I"),flag = true;
    if (f[1][n][3]) printf("N"),flag = true;
    if (f[1][n][4]) printf("G"),flag = true;
    if (!flag) printf("The name is wrong!");
    return 0;
}

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 = 105;
int dp[N][N][12],sum[N][2];
int f[N][12],s[N];
int n,m,K;

inline int read() {
    int x = 0,f = 1;char ch=getchar();
    for (; !isdigit(ch); ch=getchar()) if(ch=='-')f=-1;
    for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

void solve1() {
    for (int i=1; i<=n; ++i) s[i] = s[i-1] + read();
    memset(f,-0x3f,sizeof(f));
    f[0][0] = 0; 
    for (int i=1; i<=n; ++i) { // 到第i个位置 
        f[i][0] = 0;
        for (int j=1; j<=K; ++j) { // 选了j个矩阵 
            f[i][j] = f[i-1][j]; // 不选i 
            for (int k=0; k<i; ++k) { // 选i，那么i在的矩阵（当前矩阵）为[k+1~i]行。 
                f[i][j] = max(f[i][j],f[k][j-1]+s[i]-s[k]);
            }
        }
    }
    cout << f[n][K];
}
void solve2() {
    for (int i=1; i<=n; ++i) 
        for (int j=1; j<=m; ++j) 
            sum[i][j] = sum[i-1][j] + read();
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0][0] = 0;
    for (int i=0; i<=n; ++i) dp[i][0][0] = dp[0][i][0] = 0;
        
    for (int i=1; i<=n; ++i) { // 左边一列 
        for (int j=1; j<=n; ++j) { // 右边一列 
            dp[i][j][0] = 0;
            for (int k=1; k<=K; ++k) { // 选了k个矩阵 
                dp[i][j][k] = max(dp[i-1][j][k],dp[i][j-1][k]); // 当前这个位置不选 
                for (int p=0; p<i; ++p) // 选i，其构成的当前矩阵是左边一列[p+1~i]行 
                    dp[i][j][k] = max(dp[i][j][k],dp[p][j][k-1]+sum[i][1]-sum[p][1]);  
                for (int p=0; p<j; ++p) // 当前矩阵是右边一列[p+1~i]行 
                    dp[i][j][k] = max(dp[i][j][k],dp[i][p][k-1]+sum[j][2]-sum[p][2]);
                if (i==j) {
                    for (int p=0; p<i; ++p) // 当前矩阵是左右两列的 [p+1~i]行 
                        dp[i][j][k] = max(dp[i][j][k],dp[p][p][k-1]+sum[i][1]-sum[p][1]+sum[j][2]-sum[p][2]);
                }
            }
        }
    }
    cout << dp[n][n][K]; 
}
int main() {
    n = read(),m = read(),K = read();
    if (m==1) solve1();
    else solve2();
    return 0;
}
/*
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 = 20010;
int head[N],nxt[N<<1],to[N<<1],dp[N][2];
int n,m,Enum;

inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
    for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
    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][1] = dp[u][0] = 1;
    for (int i=head[u]; i; i=nxt[i]) {
        int v = to[i];
        if (v==fa) continue;
        DP(v,u);
        dp[u][1] += min(dp[v][1]-1,dp[v][0]);
        dp[u][0] += min(dp[v][0]-1,dp[v][1]);
    }
}
int main () {
    n = read(),m = read();
    for (int i=1; i<=m; ++i) {
        int c = read();
        dp[i][c] = 1;dp[i][c^1] = INF;
    }
    for (int i=1; i<n; ++i) {
        int u = read(),v = read();
        add_edge(u,v);
    }
    DP(n,0);
    cout << min(dp[n][1],dp[n][0]);    
    return 0;
}

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 = 50010;
const int mod = 10007;
int a[N],f[N][2],q[N],sum[N],n,m;

inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
    for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
    return x * f;
}

bool check(int x) {
    int cnt = 1,sum = 0; // zz的写成sum=1... 
    for (int i=1; i<=n; ++i) {
        sum += a[i];
        if (sum > x) {
            sum = a[i];
            cnt ++;
            if (cnt == m + 2) return false;
        }
    }
    return true;
}
int main () {
    n = read(),m = read();
    int L = 0,R = 0,mid,ans;
    for (int i=1; i<=n; ++i) {
        a[i] = read();
        L = max(L,a[i]),R += a[i];
        sum[i] = sum[i-1] + a[i];
    }
    while (L <= R) {
        mid = (L + R) / 2;
        if (check(mid)) ans = mid,R = mid - 1;
        else L = mid + 1;
    }
    cout << ans << ' ';
    
    int cur = 0,Ans = 0,tot;
    for (int i=1; i<=n; ++i) f[i][cur] = sum[i]<=ans; // 划分了0次 
    for (int j=1; j<=m; ++j) { 
        cur ^= 1; 
        tot = 0,L = 1;
        for (int i=1; i<=n; ++i) {
            while (L < i && sum[i]-sum[L] > ans) 
                tot = (tot - f[L++][cur^1] + mod) % mod;
            f[i][cur] = tot; // 到第i个位置，划分了j次。 
            tot = (tot + f[i][cur^1]) % mod;
        }
        Ans = (Ans + f[n][cur]) % mod;
    }
    cout << Ans;    
    return 0;
}

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[1010][1010];
const int mod = 10000;

inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
    for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
    return x * f;
}

int main () {
    int n,k;
    cin >> n >> k;
    f[1][0] = 1;
    for (int i=2; i<=n; ++i) {
        int sum = 0;
        int limit = min((i*(i-1))/2,k);
        
        for (int j=0; j<=limit; ++j) {
            sum = (sum + f[i-1][j]) % mod;
            if (j - i >= 0) sum = (sum - f[i-1][j-i] + mod) % mod;
            f[i][j] = sum;
        }
    }
    cout << f[n][k];
    return 0;
}

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

/*
1、求两个字符串的最长公共子序列，n^2
2、求最长的公共子序列有多少个，在第一问的基础上再加几次转移。 
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 5010;
const int mod = 100000000;
int f[2][N],g[2][N];
char a[N],b[N];

int main () {
    scanf("%s%s",a+1,b+1);
    int A = strlen(a+1) - 1,B = strlen(b+1) - 1;
    
    for (int i=0; i<=B; ++i) g[0][i] = 1;g[1][0] = 1;
    int cur = 0;
    for (int i=1; i<=A; ++i) {
        cur ^= 1;
        for (int j=1; j<=B; ++j) {
            if (a[i] == b[j]) {
                f[cur][j] = f[cur^1][j-1] + 1;
                g[cur][j] = g[cur^1][j-1];
                if (f[cur][j] == f[cur][j-1]) g[cur][j] = (g[cur][j] + g[cur][j-1]) % mod;
                if (f[cur][j] == f[cur^1][j]) g[cur][j] = (g[cur][j] + g[cur^1][j]) % mod;
            } 
            else {
                f[cur][j] = max(f[cur][j-1],f[cur^1][j]);
                g[cur][j] = 0;
                if (f[cur][j] == f[cur][j-1]) g[cur][j] = (g[cur][j] + g[cur][j-1]) % mod;
                if (f[cur][j] == f[cur^1][j]) g[cur][j] = (g[cur][j] + g[cur^1][j]) % mod;
                if (f[cur][j] == f[cur^1][j-1]) g[cur][j] = (g[cur][j] - g[cur^1][j-1] + mod) % mod;//减去重复计算的 
            }
        }
    }
    cout << f[cur][B] << "
" << g[cur][B];    
    return 0;
}

bzoj 3191 [JLOI2013]卡牌游戏

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

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

int main() {
    int n = read(),m = read();
    for (int i=1; i<=m; ++i) a[i] = read();
    
    f[1][1] = 1.0;
    for (int i=2; i<=n; ++i) { // 人数i 
        for (int j=1; j<=i; ++j) { // 获胜玩家j 
            for (int k=1; k<=m; ++k) { // 卡牌k 
                int t = a[k] % i; if (t==0) t = i; // 出局玩家t 
//                if (t == j) continue;
                f[i][j] += f[i-1][(j-t+i)%i] / (1.0 * m); // t出局后，所有玩家编号-t，j就成了 j-t 
            }
        }
    }
    for (int i=1; i<n; ++i) 
        printf("%.2lf%% ",f[n][i]*100.0);
    printf("%.2lf%%",f[n][n]*100.0);
        return 0;
}

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 205; 

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=1; i<=n; ++i) 
        T[i].a = read(),T[i].b = read();
    
    sort(T+1,T+n+1);
    for (int i=1; i<=n; ++i) sum[i] = sum[i-1] + T[i].a;
    
    memset(f,0x3f,sizeof(f));
    int ans = f[0][0];
    f[0][0] = 0; 
    
    for (int i=1; i<=n; ++i) {
        for (int j=0; j<=sum[i-1]; ++j) { 
            // 第i个人在二号窗口，后面的取max为都吃完的时间。二号窗口的变动体现在，第一维从i-1到了i（即从i-1转移），sum[i]也就发生了变化。 
            f[i][j] = min(f[i][j], max(f[i-1][j], sum[i-1]-j+T[i].a+T[i].b)); 
            // 在一号窗口 
            f[i][j+T[i].a] = min(f[i][j+T[i].a], max(f[i-1][j], j+T[i].a+T[i].b)); 
        }
    }
    for (int i=0; i<=sum[n]; ++i) ans = min(ans,f[n][i]);
    cout << ans;
    return 0;
}

bzoj 1046 [HAOI2007]上升序列 

/*
求出每个点往后的最长上升子序列，判断。 
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

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

int find(int l,int r,int x) { // 单调递减-查找第一个大于x的数 
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (g[mid] > x) ans = mid,l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}
int main() {
    int n = read();
    for (int i=1; i<=n; ++i) a[i] = read();
    
    int len = 1;
    f[n] = 1;g[len] = a[n];
    for (int i=n-1; i>=1; --i) {
        if (a[i] < g[len]) len++,g[len] = a[i],f[i] = len;
        else {
            int pos = find(1,len,a[i]);
            g[pos+1] = max(g[pos+1],a[i]); // -写成了min。。。 
            f[i] = pos + 1;
        }        
    }
    
    int m = read(),t,last;
    while (m--) {
        t = read();
        if (t > len) {puts("Impossible");continue;}
        last = 0;
        for (int i=1; ; ++i) {
            if (f[i] >= t && a[i] > a[last]) {
                printf("%d ",a[i]);
                last = i;
                t --;
                if (!t) break;
            }
        }
        puts("");
    }
    return 0;
}

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
 
const int N = 1005;
int g[N][N],a[N],f[2][N][N];
 
int main() {
    int n = read();
    for(int i=1; i<=n; ++i) 
        for (int j=1; j<=n; ++j) g[i][j] = read();
    int tot = 0;
    while (scanf("%d",&a[++tot]) != EOF) ;
     
    memset(f,0x3f,sizeof(f));
    int cur = 1;
    f[cur][1][2] = g[3][a[1]];
    f[cur][1][3] = g[2][a[1]];
    f[cur][2][3] = g[1][a[1]];
     
    for (int i=2; i<=tot; ++i) {
        cur ^= 1;
        memset(f[cur],0x3f,sizeof(f[cur]));
        for (int j=1; 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^1][j][k]+g[a[i-1]][a[i]]); 
                // 当前三辆车的位置为a[i-1],k,a[i]，所以枚举一个j，从j转移到a[i] 
                f[cur][a[i-1]][k] = f[cur][k][a[i-1]] = min(f[cur][a[i-1]][k],f[cur^1][j][k]+g[j][a[i]]);
                // 当前三辆车的位置为a[i-1],j,a[i]，所以枚举一个k，从k转移到a[i]
                f[cur][a[i-1]][j] = f[cur][j][a[i-1]] = min(f[cur][a[i-1]][j],f[cur^1][j][k]+g[k][a[i]]);
            }
        }
    }
    int ans = 0x7fffffff;
    for (int i=1; i<=n; ++i) 
        for (int j=1; j<=n; ++j) 
            ans = min(ans,f[cur][i][j]);
    cout << ans;
    return 0;
}

bzoj 1996 [Hnoi2010]chorus 合唱队

/*

想出dp的状态表示！ 

*/

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 1005;
const int mod = 19650827;
int f[N][N][2],a[N]; 

int main() {
    int n = read();
    for (int i=1; i<=n; ++i) 
        a[i] = read(),f[i][i][0] = 1;
    for (int i=n; i>=1; --i) {
        for (int j=i+1; j<=n; ++j) { // 区间i~j 
            if (a[j] > a[i]) f[i][j][1] += f[i][j-1][0];
            if (a[j] > a[j-1]) f[i][j][1] += f[i][j-1][1];
            if (a[i] < a[j]) f[i][j][0] += f[i+1][j][1];
            if (a[i] < a[i+1]) f[i][j][0] += f[i+1][j][0];
            if (f[i][j][1] > mod) f[i][j][1] %= mod;
            if (f[i][j][0] > mod) f[i][j][0] %= mod;
        }
    }
    cout << (f[1][n][0] + f[1][n][1]) % mod;
    return 0;
}

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 105;

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

int main() {
    LL n;int tot = 0;
    cin >> n;        
    f[1] = 1,f[2] = 2;
    for (int i=3; i<=88; ++i) f[i] = f[i-1] + f[i-2];
    for (int i=88; i>=1; --i) {
        if (n >= f[i]) {
            q[++tot] = i;n -= f[i];
        }
    }
    sort(q+1,q+tot+1);
    dp[1][1] = 1;dp[1][0] = (q[1] - 1) / 2;
    for (int i=2; i<=tot; ++i) {
        dp[i][1] = dp[i-1][0] + dp[i-1][1];
        dp[i][0] = dp[i-1][0]*((q[i]-q[i-1])/2) + dp[i-1][1]*((q[i]-q[i-1]-1)/2); // 这里必须要把除以2括起来！ 
    }
    cout << dp[tot][0] + dp[tot][1];
    return 0;
}

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

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

int main() {
    int Case = read();
    while (Case--) {
        int n = read(),k = read(),p = read();
        f[0][0] = 1;
        int W = n * k; // 这里是最大的质量，其实是n+(n-1)+(n-2)+...共k个。 
        for (int i=1; i<=W; ++i) {
            for (int j=1,lim=min(i,k); j<=lim; ++j) {
                f[i][j] = (f[i-j][j-1] + f[i-j][j]) % p;
                if (i > n) f[i][j] = (f[i][j] - f[i-n-1][j-1] + p) % p;
            }
        }
        
        LL ans = 0;
        for (int i=0; i<=W; ++i) {
            for (int j=0; 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-1]) % p; // 拿0号位置的物品 
            }
        }
        cout << ans << "
";
    }
    
    return 0;
}

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 = 1010;
const int mod = 7777777;
long long f[N][N][2];

int main() {
    int n;cin >> n;
    f[1][0][0] = 1;
    for (int i=2; i<=n; ++i) {
        for (int j=0; j<=n; ++j) {
            f[i][j][1] = (f[i-1][j][1] + f[i-1][j-1][1] + f[i-1][j-1][0] * 2) % mod;
            f[i][j][0] = (f[i-1][j+1][1] * j + f[i-1][j+1][0] * (j+1)) % mod;
            f[i][j][0] = (f[i][j][0] + f[i-1][j][1] * (i-j-1) + f[i-1][j][0] * (i-j-2)) % mod;
        }
    }
    cout << f[n][0][0];
    return 0;
}

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 = 5005;
int f[2][N];
 
int main() {
    int n,p;cin >> n >> p;
    if (n==1) return !printf("1");
     
    int cur = 1;
    f[1][1] = 1;
    for (int i=2; i<=n; ++i) {
        cur ^= 1;
        for (int j=1; j<=n; ++j)     
            f[cur][j] = (f[cur][j-1] + f[cur^1][i-j]) % p;
    }
    cout << (f[cur][n] * 2) % p;
    return 0;
}

bzoj 1966 [Ahoi2005]VIRUS 病毒检测

/*
开始想的dp，第一个匹配到哪，第二个匹配到哪，能不能匹配上。
然后发现复杂度有点大，看题解。。。就是这样。。。 
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 505;
bool f[N<<1][N];
char a[N<<1],b[N]; // char a[N],b[N>>1]！ 
int c[N<<1]; // int c[N]！ 

bool solve(int n,int m) {
    memset(f,false,sizeof(f));
    memset(c,0x3f,sizeof(c));
    f[0][0] = true;
    for (int i=1; i<=n; ++i) {
        if (a[i] != '*') {
            for (int j=1; j<=m; ++j) {
                if (a[i] == '?' || a[i] == b[j]) {
                    f[i][j] |= f[i-1][j-1];
                    if (a[i-1] == '*' && c[i-1] < j) f[i][j] = 1;
                }
            }
        }
        else {
            if (i==1) f[i][0] = true;
            for (int j=1; j<=m; ++j) {
                f[i][j] = (f[i-1][j] | f[i][j-1]);
                if (f[i][j]) c[i] = min(c[i],j);
            }
        }
    }
    if (f[n][m]) return false;
    return true;
}
int main() {
    scanf("%s",a+1);int n = strlen(a+1);
    int q = read(),ans = 0;
    while (q--) {
        scanf("%s",b+1);
        int m = strlen(b+1);
        if (solve(n,m)) ans ++;
    }
    cout << ans;
    return 0;
}

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const LL INF = 1e18;
const int N = 1e5+10;
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=1; i<=n; ++i) 
        a[i] = read(),b[i] = read();
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    if (n == 1 && a[1] == b[1]) return !printf("-1");
    f[1] = get(a[1],b[1]);
    f[2] = min(f[1]+get(a[2],b[2]),get(a[1],b[2])+get(a[2],b[1]));
    for (int i=3; i<=n; ++i) {
        f[i] = f[i-1] + get(a[i],b[i]);
        f[i] = min(f[i],f[i-2]+get(a[i-1],b[i])+get(b[i-1],a[i]));
        f[i] = min(f[i],f[i-3]+get(a[i],b[i-2])+get(a[i-1],b[i])+get(a[i-2],b[i-1]));
        f[i] = min(f[i],f[i-3]+get(a[i],b[i-1])+get(a[i-1],b[i-2])+get(a[i-2],b[i]));
        f[i] = min(f[i],f[i-3]+get(a[i],b[i-2])+get(a[i-1],b[i-1])+get(a[i-2],b[i]));
    }
    cout << f[n];
    return 0;
}

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 2e5+10;
const int M = 1e3+10;
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=1; i<=n; ++i) {
        A[i].x = read(),A[i].y = read(),A[i].w = read();
    }
    sort(A+1,A+n+1);
    f[1] = 0;pos[1] = 1;
    for (int i=1; i<=n; ++i) {
        int t = -0x7fffffff;
        for (int j=1; 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 0;
}

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 2010;
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 = 0;
    for (int i=1; i<=n; ++i) 
        h[i].a = read(),h[i].b = read(),sum += h[i].a;
    sort(h+1,h+n+1);
    memset(f,-1,sizeof(f));
    f[0] = sum;
    int H = read(),ans = 0;
    for (int i=1; i<=n; ++i) {
        for (int j=ans; j>=0; --j) {
            if (f[j] + h[i].b >= H) f[j+1] = max(f[j+1],f[j]-h[i].a);
        }
        if (f[ans+1] >= 0) ans++;
    }
    cout << ans;
    return 0;
}

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 2010;
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=1; i<=n; ++i) {
        int a = read(),b = read(),s = read(),t = read();
        for (int j=0; j<=s; ++j) f[i][j] = -a*j; // 买入 
        for (int j=0; j<=m; ++j) f[i][j] = max(f[i][j],f[i-1][j]); // 卖出 
        if (i <= w) continue;
        L = 1,R = 0;
        for (int j=0; j<=m; ++j) { // 买入 
            while (L <= R && q[L] < j - s) L++; // 最多买s股，保证买的合法
            while (L <= R && f[i-w-1][q[R]]+q[R]*a <= f[i-w-1][j]+j*a) R--; // 每次取大的，保证转移的点最优 
            q[++R] = j;
            if (L <= R) f[i][j] = max(f[i][j],f[i-w-1][q[L]]+q[L]*a-j*a); 
        }
        L = 1,R = 0;
        for (int j=m; j>=0; --j) { // 卖出 
            while (L <= R && q[L] > j + t) L ++; // --j + b
            while (L <= R && f[i-w-1][q[R]]+q[R]*b <= f[i-w-1][j]+j*b) R--;
            q[++R] = j;
            if (L <= R) f[i][j] = max(f[i][j],f[i-w-1][q[L]]+q[L]*b-j*b);
        }
    }
    int ans = 0;
    for (int i=0; i<=m; ++i) ans = max(ans,f[n][i]);
    cout << ans;
    return 0;
}

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
 
#define Rep(i,a,b) for (int i = (a); i <= b; ++ i)
const int N = 55;
const int M = 10005;
int f[N][M],U[N],d[N];
 
int main() {
    int n = read(),m = read(),S = read();
    Rep (i,1,n) U[i] = read();
    Rep (i,1,n) d[i] = read();
    memset(f,0x3f,sizeof(f));
    f[0][0] = 0;
    Rep (i,1,n) {
        int res = 1e9,k = 0;
        Rep (j,0,S) {
            while (k <= min(j+U[i],S)) { 
                res = min(res, f[i-1][k] + (m - d[i]) * k); k++;
            }
            f[i][j] = res + (j + U[i]) * d[i];
        }
    }
    cout << f[n][0];
    return 0;
}

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
 
const int N = 100010;
 
int head[N],nxt[N<<1],to[N<<1],Enum;
LL f[N][11][3],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 0;
    return t % mod ? t % mod : mod; // --
}
void dfs(int u,int fa) {
    for (int i=0; i<=10; ++i) f[u][i][0] = 1;
    for (int i=head[u]; i; i=nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        dfs(v,u);
        for (int j=0; j<=10; ++j) {
            LL f0 = !j ? 0 : f[v][j-1][0] + f[v][j-1][1] + f[v][j-1][2];  // 不向这个儿子连边 
            LL f1 = f[v][j][0] + f[v][j][1]; // 向这个儿子连边 
            LL tmp = f[u][j][2] * f0 + f[u][j][1] * f1; f[u][j][2] = get(tmp); //原来2条*现在0条，原来1条*现在1条 
            tmp = f[u][j][1] * f0 + f[u][j][0] * f1; f[u][j][1] = get(tmp); //原来1条*现在0条，原来1条*现在1条 
            tmp = f[u][j][0] * f0; f[u][j][0] = get(tmp);//原来0条*现在0条 
        }
    }
}
int main() {
    int n = read(),m = read(); mod = read();
    for (int i=1; i<=m; ++i) {
        int u = read(),v = read();
        add_edge(u,v);add_edge(v,u);
    }
    if (m != n - 1) {
        puts("-1
-1");return 0;  // --
    }
    dfs(1,0);
    LL ans;
    for (int i=0; i<=10; ++i) {
        if (ans = f[1][i][0] + f[1][i][1] + f[1][i][2]) {
            printf("%d
%d",i,ans%mod);
            break;
        }
    }
    return 0;
}

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
 
const int N = 205;
const int INF = 1e9;
int head[N],nxt[N<<1],to[N<<1],len[N<<1],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] != -1) return f[i][j][k];
    f[i][j][k] = INF;
    int res = 0;
    for (int t=0; t<=j; ++t) {
        res = 0;
        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 = 0;
            if (ls[i]) res += dp(ls[i],t,i); // 建伐木场 
            if (rs[i]) res += dp(rs[i],j-t-1,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,-1,sizeof(tr));
    for (int i=1; i<=n; ++i) {
        w[i] = read();
        int x = read(), len = read();
        if (tr[x] == -1) ls[x] = i,tr[x] = i;
        else rs[tr[x]] = i,tr[x] = i;
        add_edge(x,i,len);
    }
    dfs(0,0);
    memset(f,-1,sizeof(f));
    printf("%d
",dp(0,m,0));
    return 0;
}

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 = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}

int f[2][105], h[100100];

int main() {
    freopen("phonewire.in","r",stdin);freopen("phonewire.out","w",stdout);
    int n = read(), c = read();
    for (int i=1; i<=n; ++i) h[i] = read();
    int cur = 1;
    for (int i=h[1]; i<=100; ++i) f[cur][i] = (i - h[1]) * (i - h[1]);
    for (int i=2; i<=n; ++i) {
        cur ^= 1;
        memset(f[cur], 0x3f, sizeof(f[cur]));
        for (int res=1e9,j=0; j<=100; ++j) {
            if (j >= h[i - 1]) res = min(res, f[cur ^ 1][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=100; j>=0; --j) {
            if (j >= h[i - 1]) res = min(res, f[cur ^ 1][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=0; i<=100; ++i) ans = min(ans, f[cur][i]);
    cout << ans;
    return 0;
}

－－－－－－－－