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

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;
}
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

1 条评论

boshi · 2017年5月30日 9:36 下午

%%%董事长%%%

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *