[大山中学dp常练-4 Rounds]

2023-01-08 15:18:27

Round#1 2016.9.28

这次晚练十分sb 有点浪费时间全是dp题

先说过程 3分钟草了第一题之后感觉好像有点水然后翻了翻题目看了看第一第四题两颗星其他三颗星然后一下子第二题题目太长就兴起草第三题打了四十五分钟然后草第二题然后就没了要收卷(第二题还没调完给多我五分钟就A了) 整体用了一个半小时吧(马力有点弱..)

三维dp 你也可以变成N和K的dp只是麻烦一点这题不会可以退役

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#define Maxn 1010

using namespace std;

int F[Maxn][][]; int T[Maxn];

int main()

{

  freopen("bcatch.in","r",stdin);

  freopen("bcatch.out","w",stdout);

  int N,K; scanf("%d%d",&N,&K); for(int i=;i<=N;i++) scanf("%d",&T[i]);

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

  {

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

    {

      F[i][j][]=max(F[i][j][],max(F[i-][j][],F[i-][j-][])+(T[i]==));

      F[i][j][]=max(F[i][j][],max(F[i-][j][],F[i-][j-][])+(T[i]==));

    }

  }

  int maxx=;

  for(int i=;i<=K;i++) for(int j=;j<=;j++) maxx=max(maxx,F[N][i][j]);

  return printf("%d\n",maxx),;

}

/*

7

2

1

1

2

2

1

1

*/

第二题题目很烦条件很多我们发现斜坡是越短越好然后用时间和能力值dp一下随便草就好了

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

using namespace std;

struct Course

{

  int m,l,a;

}C[];

bool Cmp(const Course &x,const Course &y){return x.m<y.m;}

struct XP

{

  int c,d;

}X[];

int T,S,N;

int F[][];

int L[];

int main()

{

  freopen("ski.in","r",stdin);

  freopen("ski.out","w",stdout);

  scanf("%d%d%d",&T,&S,&N);

  for(int i=;i<=S;i++) scanf("%d%d%d",&C[i].m,&C[i].l,&C[i].a);

  sort(C+,C+S+,Cmp);

  for(int i=;i<=N;i++) scanf("%d%d",&X[i].c,&X[i].d);

  for(int i=;i<=;i++) L[i]=;

  for(int i=;i<=N;i++) L[X[i].c]=min(L[X[i].c],X[i].d);

  for(int i=;i<=;i++) L[i]=min(L[i],L[i-]);

  for(int i=;i<=T;i++) for(int j=;j<=;j++) F[i][j]=-;

  F[][]=; int l=; int r=;

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

  {

    while(C[r].m==i) r++;

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

    {

      if(F[i][j]!=-)

      {

        F[i+][j]=max(F[i+][j],F[i][j]);

        if(i+L[j]<=T) F[i+L[j]][j]=max(F[i+L[j]][j],F[i][j]+);

        for(int k=l;k<r;k++) if(i+C[k].l<=T) F[i+C[k].l][C[k].a]=max(F[i+C[k].l][C[k].a],F[i][j]);

      }

    }

    l=r;

  }

  int maxx=;

  for(int i=;i<=T;i++) for(int j=;j<=;j++) maxx=max(maxx,F[i][j]);

  return printf("%d\n",maxx),;

}

/*

10 1 2

3 2 5

4 1

1 3

*/

第三题也想了一会儿我们发现有一些状态我们是一定到不了的就好比

7 3

8 5

其实8的时候最多为4 就改一下还有一种

7 3

8 1

那么你7是要改成2的

先从后面扫一遍然后前面再扫一遍到后面(先后顺序不知道可不可以换应该可以吧考场上没多想)

剩下的话都是可以到的然后每次都到这个速度就是最优的因为你如果合法但是又小于这个速度就是最差的那么的话每两个点之间你就把它们先升到一个高度然后再往上飞最长的一段再下来

最后还要判断一下到终点 (就这样没了两个点)

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#define Maxn 100010

using namespace std;

bool Cmp(const pair<int,int> &x,const pair<int,int> &y){if(x.first!=y.first) return x.first<y.first; return x.second>y.second;}

int L,M; pair<int,int>pr[Maxn];

int F[Maxn];

int main()

{

  freopen("bobsled.in","r",stdin);

  freopen("bobsled.out","w",stdout);

  scanf("%d%d",&L,&M); for(int i=;i<=M;i++) scanf("%d%d",&pr[i].first,&pr[i].second);

  sort(pr+,pr+M+,Cmp); memset(F,,sizeof(F)); F[]=;

  for(int i=;i<=M;i++) F[i]=min(F[i],pr[i].second);

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

  {

    if(pr[i].first!=pr[i+].first)

    {

      F[i]=min(F[i],F[i]+(F[i+]-F[i])+(pr[i+].first-pr[i].first));

    }

    else F[i]=F[i+];

  } int l;

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

  {

    l=i; while(pr[l].first==pr[l+].first) l++;

    if(pr[l].first!=pr[i-].first)

    {

      F[l]=min(F[l],F[l]+((F[i-]-F[l])+(pr[l].first-pr[i-].first)));

    }

    for(int j=i;j<=l;j++) F[j]=F[l];

  }

  int ans=;

  for(int i=;i<=M;i++) ans=max(ans,max(F[i],F[i-])+(pr[i].first-pr[i-].first-abs(F[i]-F[i-]))/);

  ans=max(ans,F[M]+(L-pr[M].first));

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

}

/*

14 3

7 3

11 1

13 8

*/

看看范围好像直接背包会爆很明显这道题给出来的做法一定是NM 然后想想背包可不可以换种方式

看到都是M的倍数也就是说 M以上的都可以变成小于M咯其它也要保留一下然后F[N][i]表示现在放到第I个物品然后M的倍数+i 然后再用一个数组辅助转移搞一下就好了差不多绕圈的dp

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#define Maxn 2010

using namespace std;

const int Mod=1e8;

int N,M; int A[Maxn]; int F[Maxn]; bool bo[Maxn]; int G[Maxn];

int main()

{

  freopen("fristeam.in","r",stdin);

  freopen("fristeam.out","w",stdout);

  scanf("%d%d",&N,&M);

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

  memset(F,,sizeof(F)); F[]=; memset(G,,sizeof(G)); memset(bo,,sizeof(bo)); bo[]=;

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

  {

    for(int j=;j<M;j++) G[j]=;

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

      if(bo[j]) G[(j+A[i])%M]=(G[(j+A[i])%M]+F[j])%Mod,bo[(j+A[i])%M]=;

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

      if(bo[j]) F[j]=(F[j]+G[j])%Mod;

  }

  return printf("%d\n",F[]-),;

}

/*

4 5

1

2

8

2

*/

Round #2 2016.9.29

这次题目好像上了点难度，有点意思了

第一题考场上看错题意以为中间有一个高的就不能跨过去其它都可以..

当我back回的时候才发现那条线要是直的所以的话用斜率搞一下画画图很容易把O(N^3)变成O(N^2)

有空再更..

码农公寓

相关文章