试题收录,序列计数
分类:计算机网络

动态规划 试题收录,规划试题收录

DP稀烂也不是一天两天了

我觉得我很有必要把做(chao)过的DP记录下来啊... ...DP这种精细的东西真是太玄妙了。

慢慢来吧。只有思维足够强大,才足以见题拆题。

编辑中... ...

 

树形DP:

1.机器人采集金属

分析:设 f[i][j] 为:遍历完j的子树,且剩下i个回到j的最小代价。特殊的,f[0][i]表示用一个机器人走完所有节点再回来的代价,原因是每个点都必须且只能转移一种对答案贡献的状态。

那么状态转移方程就要分两类讨论。

初始化:f[i][x]=sigma(f[0][son_i]);

维护:f[i][k]=min(f[i][k],f[i-j][son_i]+f[j][son_i]+j*Edge_val;

想想真的很妙啊。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
const int N = 100010;
struct Node{int to;LL val;int next;}E[N];
int n,S,K,tot,head[N];LL f[21][N];
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
inline void link(int u,int v,LL w)
{
  E[++tot]=(Node){v,w,head[u]};
  head[u]=tot;
}
inline void dfs(int x,int fa)
{
  for(int e=head[x];e;e=E[e].next)
    {
      int now=E[e].to;
      if(now==fa)continue;
      dfs(now,x);
      for(int k=K;k>=0;--k)
 {
   f[k][x]+=f[0][now]+2*E[e].val;
   for(int i=1;i<=k;++i)
     f[k][x]=min(f[k][x],f[k-i][x]+f[i][now]+i*E[e].val);
 }
    }
}
int main()
{
  //freopen("input.txt","r",stdin);
  //freopen("output.txt","w",stdout);
  n=gi();S=gi();K=gi();
  for(int i=1;i<n;++i)
    {
      int u=gi(),v=gi();LL w=gL();
      link(u,v,w);link(v,u,w);
    }
  dfs(S,S);printf("%lldn",f[K][S]);

  /*fclose(stdin);
    fclose(stdout);*/
  return 0;
}

 

背包问题

1.多重背包计数

考场上只打了一个01背包的暴力,但是明显没什么卵用。

然后好像RG说是FFT?弱的抠脚... ...

不过Nick讲了一种十分高明的做法:分块。

考场上我在想能不能直接把N/2的枝减掉,Nick说我可以大胆剪刀根号级。

对于根号之前的就直接暴力肛。这样前半截的复杂度在数据不超过2000下没有压力(实在是不会分析了)。

对于根号后的,记录g[i][j]表示使用i个,体积和为j的方案数。然后显然i顶多到根号n。

转移方程也是十分巧妙,给我一种点科技树的感觉。

1.加入一个体积为根号的物品;

2.背包内每个东西的值都变成其+1;

是不是巧妙无比?我是被吓到了/*哦吼*/。对了记得g[1][0](G10);

统计答案的时候,用乘法原理+加法原理,前半部分和后半部分搞一下。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <cmath>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
const int N = 100010;
const int Mod = 23333333;
LL f[5][N],g[320][N],n,lim,sum[N],now;
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
void pui(int x)
{
  if(x<10)putchar(x+'0');
  else pui(x/10),putchar(x%10+'0');
}
LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
inline void work1()
{
  for(int i=1;i<=lim;++i)
    {
      now^=1;memset(sum,0,sizeof(sum));
      for(int j=0;j<=n;++j)
 {
   f[now][j]=(sum[j%i]+f[now^1][j])%Mod;
   if(j<i*i)sum[j%i]=(sum[j%i]+f[now^1][j])%Mod;
   else sum[j%i]=((sum[j%i]-f[now^1][j-i*i]+f[now^1][j])%Mod+Mod)%Mod;
 }
    }
}
inline void work2()
{
  for(int i=0;i<=lim;++i)
    for(int j=0;j<=n;++j)
      {
 if(i&&i+j<=n)g[i][i+j]=(g[i][i+j]+g[i][j])%Mod;
 if(j+lim+1<=n)g[i+1][j+lim+1]=(g[i+1][j+lim+1]+g[i][j])%Mod;
      }
  ++g[1][0];
}
inline void calcans()
{
  LL Ans=0;
  for(int i=0;i<=n;++i)
    for(int j=1;j<=lim;++j)
      Ans=(Ans+((LL)f[now][i]*(LL)g[j][n-i])%Mod)%Mod;
  printf("%lldn",Ans);
}
int main()
{
  n=gi();lim=sqrt(n);f[0][0]=g[0][0]=1;
  work1();work2();calcans();return 0;
}

 

 

数学等类

1.机器人m号

这题的正解有两种,DP和递推(其实也是一个DP)。关于第二种,我发现它的状态设置的十分巧妙,对欧拉函数的积性运用到了很高的境界。

容易发现独立数就是欧拉函数。所以答案就是要求一个数的所有因子:

1.由奇数个不同的奇质因子组成的因子的欧拉函数的和。

2.由偶数个不同的奇质因子组成的因子的欧拉函数的和。

3.其他所有因子的欧拉函数的和。

然后由欧拉函数的性质我们发现第3个不用求,重点在前两个。

用莫比乌斯函数推是没用的,因为没有2。可以考虑DP;

朴素的DP就是f[i][j]表示推到第i个质数,由j个不同奇质数组成的数的欧拉函数和,然后答案就是两个累加。这也是很巧妙的利用了积性。

第二种就更加简单粗暴,但这正是世界的美丽。设Ans1和Ans2分别就是f对应的奇偶状态的和。一路读入一路递推就可以了。递推式也简介务必让人shiniao未及,吓得我一抖一抖的。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
const LL Mod = 10000;
LL F[1010][1010],Ans1,Ans2,m,k;
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
void pL(LL x)
{
  if(x<0)putchar('-'),pL(-x);
  if(x<10)putchar(x+'0');
  else pL(x/10),putchar(x%10+'0');
}
void pc(){putchar('n');}
LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
LL Qpow(LL d,LL z)
{
  LL ans=1;
  for(;z;z>>=1,d=d*d%Mod)if(z&1)ans=ans*d%Mod;
  return ans;
}
int main()
{
  k=gL();m=1;
  for(LL i=1;i<=k;++i)
    {
      LL p=gL(),e=gL();
      m=m*Qpow(p,e)%Mod;
      if(p==2)continue;
      LL ans1=(Ans1+(Ans2+1)*(p-1))%Mod;
      LL ans2=(Ans2+Ans1*(p-1))%Mod;
      Ans1=ans1;Ans2=ans2;
    }
  pL(Ans2);pc();pL(Ans1);pc();pL(((m-Ans1-Ans2-1)%Mod+Mod)%Mod);
  return 0;
}

 

试题收录,规划试题收录 DP稀烂也不是一天两天了 我觉得我很有必要把做(chao)过的DP记录下来啊... ...DP这种精细的东西真是太玄妙...

刚出炉的省选题,还是山东的。

自古山东出数学和网络流,堪称思维的殿堂,比某地数据结构成风好多了。

废话不说上题解。

1.题面

  求:n个数(顺序可更改),值域为[1,m],和为p的倍数,且这些数里面有质数的方案数是多少?

解题报告:

  0% O(n^n)爆搜,没什么好讲的,用来拍DP;

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int N = 20000010;
int n,P[N],tot,m,k;
LL Ans,tim;
bool vis[N];
inline int gi()
{
    int x=0,res=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')res=-res;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x*res;
}

inline void shai()
{
    vis[1]=1;
    for(int i=2;i<=m;++i)
        {
            if(!vis[i])P[++tot]=i;
            for(int j=1;j<=tot;++j)
                {
                    if(i*P[j]>m)break;
                    vis[i*P[j]]=true;
                    if(i%P[j]==0)break;
                }
        }
}

inline void dfs(int dep,int flag,int sum)
{
    if(dep==n){if(flag==1&&(sum%k==0))Ans++;return;}
    for(int x=1;x<=m;++x)
        if(vis[x]==false)dfs(dep+1,1,sum+x);
        else dfs(dep+1,flag,sum+x);
}
int main()
{
    freopen("in.txt","r",stdin);
    freopen("BL.txt","w",stdout);
    n=gi();m=gi();k=gi();shai();
    dfs(0,0,0);cout<<Ans%20170408<<endl;
}

  

  30% O(nmp)DP;

    注意到每一个数可以任意取,就是很显然的具有DP性质了。那么有两种DP方法:

      1.f[i][j][0/1]表示第i个数,模p为j,有无质数的情况;这种我写到一半停下来了,因为我发现了第二种DP可以优化。

      2.f[i][j]和g[i][j]分别表示瞎几把乱取数和不取质数的情况,求出后相减即可(容斥思想)。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int N = 20000010;
const int Mod = 20170408;
int n,P[N],tot,m,p,f[10100][101];
LL Ans,tim;
bool vis[N];

inline int gi()
{
    int x=0,res=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')res=-res;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x*res;
}

inline void shai()
{
    vis[1]=1;
    for(int i=2;i<=m;++i)
        {
            if(!vis[i])P[++tot]=i;
            for(int j=1;j<=tot;++j)
                {
                    if(i*P[j]>m)break;
                    vis[i*P[j]]=true;
                    if(i%P[j]==0)break;
                }
        }
}

int main()
{
    freopen("in.txt","r",stdin);
    freopen("DP.txt","w",stdout);
    n=gi();m=gi();p=gi();shai();
    f[0][0]=1ll;
    for(int i=0;i<n;++i)
        for(int j=0;j<p;++j)
            for(int k=1;k<=m;++k)
                {
                    f[i+1][(j+k)%p]+=f[i][j];
                    if(f[i+1][(j+k)%p]>Mod)
                        f[i+1][(j+k)%p]-=Mod;
                }
    Ans=(LL)f[n][0];
    memset(f,0,sizeof(f));f[0][0]=1ll;
    for(int i=0;i<n;++i)
        for(int j=0;j<p;++j)
            for(int k=1;k<=m;++k)
                {
                    if(!vis[k])continue;
                    f[i+1][(j+k)%p]+=f[i][j];
                    if(f[i+1][(j+k)%p]>Mod)
                        f[i+1][(j+k)%p]-=Mod;
                }
    Ans-=(LL)f[n][0];
    printf("%lldn",(Ans%Mod+Mod)%Mod);
}

  

   80%:我们发现状态转移方程是一个第一维线性递推,第二维稳定一阶转移。然后发现p只有100,于是就可以上矩阵快速幂。建立转移矩阵就是上面的DP式子。复杂度O(mp+p^3logn)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int N = 20000010;
const int Mod = 20170408;
struct Matrix{
    int T[105][105];
}S0,M0,M1;
int n,P[N],tot,m,p;
LL Ans;
bool vis[N];

inline int gi()
{
    int x=0,res=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')res=-res;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x*res;
}

inline void shai()
{
    vis[1]=1;
    for(int i=2;i<=m;++i)
        {
            if(!vis[i])P[++tot]=i;
            for(int j=1;j<=tot;++j)
                {
                    if(i*P[j]>m)break;
                    vis[i*P[j]]=true;
                    if(i%P[j]==0)break;
                }
        }
}

inline Matrix Mul(Matrix a,Matrix b,int I,int K,int J)
{
    Matrix S=S0;
    for(int i=0;i<I;++i)
        for(int j=0;j<J;++j)
            for(int k=0;k<K;++k)
                S.T[i][j]=((LL)(S.T[i][j])+((LL)a.T[i][k]*(LL)b.T[k][j]%Mod))%Mod;
    return S;
}

inline Matrix Qpow(Matrix s,Matrix d,int z,int I,int K,int J)
{
    Matrix S=s;
    for(;z;z>>=1,d=Mul(d,d,I,K,J))
        if(z&1)S=Mul(S,d,I,K,J);
    return S;
}

int main()
{
    freopen("in.txt","r",stdin);
    freopen("MT.txt","w",stdout);
    n=gi();m=gi();p=gi();shai();
    M0.T[0][0]=1ll;
    for(int i=0;i<p;++i)
        for(int j=1;j<=m;++j)
            {
                M1.T[i][(i+j)%p]++;
                M1.T[i][(i+j)%p]%=Mod;
            }
    Matrix ans1 = Qpow(M0,M1,n,p,p,p);
    Ans+=ans1.T[0][0];M0=M1=S0;M0.T[0][0]=1ll;
    for(int i=0;i<p;++i)
        for(int j=1;j<=m;++j)
            {
                if(!vis[j])continue;
                M1.T[i][(i+j)%p]++;
                M1.T[i][(i+j)%p]%=Mod;
            }
    Matrix ans2 = Qpow(M0,M1,n,p,p,p);
    Ans-=ans2.T[0][0];
    printf("%lldn",(Ans%Mod+Mod)%Mod);
}

  

   100%:我们发现时间TLE在于构建矩阵时的mp太大,然后我们发现这个转移重复了很多次,于是可以通过预处理贡献优化到p^2; 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int N = 20000010;
const int Mod = 20170408;
struct Matrix{
    int T[105][105];
}S0,M0_1,M1_1,M0_2,M1_2,ans;
int n,P[N],tot,m,p,foo[200];
LL Ans;
bool vis[N];

inline int gi()
{
    int x=0,res=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')res=-res;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x*res;
}

inline void shai()
{
    vis[1]=1;
    for(int i=2;i<=m;++i)
        {
            if(!vis[i])P[++tot]=i;
            for(int j=1;j<=tot;++j)
                {
                    if(i*P[j]>m)break;
                    vis[i*P[j]]=true;
                    if(i%P[j]==0)break;
                }
        }
}

inline Matrix Mul(Matrix a,Matrix b,int I,int K,int J)
{
    Matrix S=S0;
    for(int i=0;i<I;++i)
        for(int j=0;j<J;++j)
            for(int k=0;k<K;++k)
                S.T[i][j]=(S.T[i][j]+(LL)a.T[i][k]*b.T[k][j])%Mod;
    return S;
}

inline Matrix Qpow(Matrix S,Matrix d,int z,int I,int K,int J)
{
    for(;z;z>>=1,d=Mul(d,d,I,K,J))
        if(z&1)S=Mul(S,d,I,K,J);
    return S;
}

int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    n=gi();m=gi();p=gi();shai();
    M0_1.T[0][0]=M0_2.T[0][0]=1ll;
    for(int i=1;i<=m;++i)++foo[i%p];
    for(int i=0;i<p;++i)
        for(int j=0;j<p;++j)
            {
                int st=(i+j)%p;
                M1_1.T[i][st]+=foo[j];
                if(M1_1.T[i][st]>=Mod)
                    M1_1.T[i][st]-=Mod;
            }
    ans = Qpow(M0_1,M1_1,n,p,p,p);
    Ans+=ans.T[0][0];
    for(int i=0;i<p;++i)foo[i]=0;
    for(int i=1;i<=m;++i)
        if(vis[i])++foo[i%p];
    for(int i=0;i<p;++i)
        for(int j=0;j<p;++j)
            {
                int st=(i+j)%p;
                M1_2.T[i][st]+=foo[j];
                if(M1_2.T[i][st]>=Mod)
                    M1_2.T[i][st]-=Mod;
            }
    ans = Qpow(M0_2,M1_2,n,p,p,p);
    Ans-=ans.T[0][0];
    printf("%lldn",(Ans%Mod+Mod)%Mod);
}

  

//然后你就华丽的AC了!

 

本文由美高梅网址发布于计算机网络,转载请注明出处:试题收录,序列计数

上一篇:没有了 下一篇:没有了
猜你喜欢
热门排行
精彩图文