动规虐我千百遍，我待动规….. 咳咳。

T1

题目来源：未知
题目描述：用第 1 个、第 2 个…第 N 个斐波那契数构成一个长度为 P 的序列，每个斐波那契数可以使用任意多次，但至少要使用一次，并且序列中任意两个相同的斐波那契数之间至少要隔着 M 个数，pf 希望知道满足条件的序列组成方法有多少种。
解题思路：做了 1 个半小时没有结果的我感觉自己已经疯了，用容斥瞎搞了一通后发现居然很多数据都可以过，然后就没管了，然后就蜜汁 A 了？不是很明白，等彻底了解容斥后再说吧。
代码：

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
long long f[1005][1005],g[1005][1005];
int n,m,p,mod=1000000007;
int main()
{
    freopen("pf.in","r",stdin);
    freopen("pf.out","w",stdout);
    int i,j;long long ans=0;
    scanf("%d%d%d",&n,&m,&p);
    if(n==m&&p>n){printf("0");return 0;}
    g[1][0]=1;g[1][1]=1;
    for(i=2;i<=n;i++){//杨辉三角求组合方法
        g[i][0]=1;
        for(j=1;j<=i;j++)
        {g[i][j]=g[i-1][j]+g[i-1][j-1];g[i][j]%=mod;}
    }
    for(j=m;j<=n;j++){
        f[j][1]=j;
        for(i=2;i<=m;i++)
            {f[j][i]=(long long)f[j][i-1]*(j-i+1);f[j][i]%=mod;}
        for(i=max(m+1,2);i<=p;i++)//注意 m=0 的情况
            {f[j][i]=(long long)f[j][i-1]*(j-m);f[j][i]%=mod;}
        if(j!=n){ans=(long long)f[j][p]*g[n][j]-ans;if(ans<0)ans+=mod;ans%=mod;}//迷一般的容斥
    }
    ans=(long long)(f[n][p]+mod)-ans;ans%=mod;
    printf("%lld",ans);
    return 0;
}

T2

题目来源：codevs1997（bzoj 上也有不过是权限题）
题目描述：略
解题思路：伪概率 dp，因为最多只有 200 块地图残片，所以背包只要开到 200 就可以了，超额的统统变成 200，然后用 f[i][j][k] 表示到第 i 场比赛为止赢了 j 场背包剩余容量为 k 的概率。正因为背包这个变，所以不能够用 f[i][j][k]=f[i-1][j-1][k-a[i]]×p[i]+f[i-1][j][k]×(1.0-p[i]) 这个公式，而要正着推。具体看代码
代码：

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
    int q=0,w=1;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q*w;
}
double f[201][201][405],p[201];//前 i 场比赛赢 j 次背包为 k
int n,l,k,a[201];
int chan(int x){//溢出的就不用算了啦
    if(x>n)x=n;
    return x+201;
}
int main()
{
    freopen("guard.in","r",stdin);
    freopen("guard.out","w",stdout);
    int i,j,t,x;double ans=0;
    n=read();l=read();k=read();
    for(i=1;i<=n;i++){x=read();p[i]=x*1.0/100.0;}
    for(i=1;i<=n;i++)a[i]=read();
    f[0][0][chan(k)]=1.0;
    for(i=0;i<n;i++)
    for(j=0;j<=i;j++)
    for(t=-i;t<=n;t++){//因为不要溢出部分，所以要正向推
        f[i+1][j+1][chan(t+a[i+1])]+=f[i][j][chan(t)]*p[i+1];
        f[i+1][j][chan(t)]+=f[i][j][chan(t)]*(1.0-p[i+1]);
    }
    for(i=l;i<=n;i++)
        for(j=0;j<=n;j++)ans+=f[n][i][chan(j)];
    printf("%.6lf",ans);
    return 0;
}

T3

题目来源：codeforces11D（多古老的题目了）
题目描述: 求大小大于 3 的简单环个数
解题思路：状压 dp，用 f[i][zt] 表示经过的点集为 zt 时，以 i 为终点可以获得的环的数量，初始化 f[i][(1<<i)]=1，因为如果要求这样一个状态，扩展出来的肯定有环。
然后做一个简化，每次从比当前起点编号大一些的点开始枚举，比如说有一个简单环 1-2-3-1，也会被枚举 1-3-2-1，所以最后得到的答案要除以 2
显然对于每一个与 i 联通的点 j，有代码中的递推式。不过如果 j 已经包含在 zt 集合中就不用算了，以后会算一个新环的。
代码:

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int maxn=(1<<20);
int n,m;long long ans;
long long dp[22][maxn];
bool l[22][22];
int getmi(int x){//寻找路径上编号最小点
    for(int i=0;i<n;i++)
        if(x&(1<<i))return i;
}
int cnt(int x){//寻找经过了几个点
    int re=0;
    for(int i=0;i<n;i++)
        if(x&(1<<i))re++;
    return re;
}
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    int i,j,x,y,up,zt;
    n=read();m=read();
    for(i=1;i<=m;i++){
        x=read();y=read();x--;y--;
        l[x][y]=l[y][x]=1;
    }
    for(i=0;i<n;i++)dp[i][(1<<i)]=1;//if 遇到可以从 i 走到 i 的情况，那么说明找到了一个简单环
    up=(1<<n)-1;
    for(zt=1;zt<=up;zt++)
        for(i=0;i<n;i++)
        if(dp[i][zt]&&(zt&(1<<i))){
        for(j=getmi(zt)+1;j<n;j++)
            if(l[i][j]&&!(zt&(1<<j)))dp[j][zt|(1<<j)]+=dp[i][zt];
    }
    for(i=0;i<n;i++)
        for(j=1;j<=up;j++)
        if(l[i][getmi(j)]&&cnt(j)>2)ans+=dp[i][j];
    printf("%lld",ans/2);
    return 0;
}

T4

题目来源：洛谷 P2627，codevs4654（bzoj 上又是权限题）
题目描述：略
解题思路：用 f[i] 表示删掉第 i 头牛使得满足条件的最小去掉牛的价值和，然后用单调队列优化 dp
代码：

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
    int q=0,w=1;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q*w;
}
long long a[100005],f[100005],que[100005],tot;
int ti[100005];
int n,m,l,r;
int main()
{
    freopen("cg.in","r",stdin);
    freopen("cg.out","w",stdout);
    int i,j;long long ans=LLONG_MAX;
    n=read();m=read();
    for(i=1;i<=n;i++)a[i]=read(),tot+=a[i];
    for(i=1;i<=n;i++){
        f[i]=a[i]+que[l];
        while(que[r]>f[i]&&l<r)r--;
        que[++r]=f[i];ti[r]=i;
        while(ti[l]<i-m)l++;//no = because 一定要剪掉这里
    }
    for(i=n-m;i<=n;i++)ans=min(ans,f[i]);
    printf("%lld",tot-ans);
    return 0;
}