2019 TCO Round 1B——[ 状压DP ]

第一题是 EllysSki 。

题意：给n个数，求两个方向的最长递减区间。

可以O(n)。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

int Mx(int a,int b){return a>b?a:b;}

class EllysSki{

public:

  int getMax(vector <int> height);

};

int EllysSki::getMax(vector <int> height)

{

  int n=height.size(),ans=;

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

    {

      int j=i;

      while(j+<n&&height[j+]<=height[j])

    j++;

      ans=Mx(ans,j-i+); i=j;

    }

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

    {

      int j=i;

      while(j&&height[j-]<=height[j])

    j--;

      ans=Mx(ans,i-j+); i=j;

    }

  return ans;

}

第二题是 EllysTeleport 。

题意：连边，找最长链。

自己写了tarjan，没调出来。其实 n² 暴力也行。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int Mx(int a,int b){return a>b?a:b;}

int Mn(int a,int b){return a<b?a:b;}

const int N=1e4+;

int n,h[N],to[N]; bool vis[N];

class EllysTeleport{

  int fnd(int x)

  {

    int l=,r=n,ret=;

    while(l<=r)

      {

    int mid=l+r>>;

    if(h[mid]<=x)ret=mid,l=mid+;

    else r=mid-;

      }

    return ret;

  }

public:

  int getMax(int N, int H1, int A, int B, int P, int Q, int M)

  {

    n=N; h[]=H1;

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

      h[i]=((ll)h[i-]*A+B)%M;

    sort(h+,h+n+);

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

      {

    int d=((ll)h[i]*P+Q)%M;

    to[i]=fnd(d);

      }

    int ans=;

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

      {

    memset(vis,,sizeof vis);

    int cnt=,cr=to[i]; vis[i]=;

    while(cr&&!vis[cr])

      {

        cnt++;vis[cr]=;cr=to[cr];

      }

    ans=Mx(ans,cnt);

      }

    return ans;

  }

};

第三题是 EllysPearls 。

题意：n(<=50) 个球排成一排，每个球是 m(<=15) 种颜色之一。一次操作可以拿出序列中任意一个球，再插进序列的任意一个位置。求最少操作次数使得相同颜色的球是一个区间。

题解：https://www.topcoder.com/blog/2019-topcoder-open-algorithm-round-1b-editorials/

颜色只有 15 ，考虑状压。 1 表示该颜色之前已经确定了一个位置，即当前球必须取出、融入之前自己颜色的区间。

特殊情况就是当前球不动，就能合法；所以再记目前最后的颜色是什么（可以是空）。

还可能遇到当前球，但是把它放在后面，即尚不确定当前颜色。发现这种情况和“融入之前自己颜色的区间”都是要花费1的代价，并且不改变状压的状态。

所以 dp[ i ][ j ][ s ] 表示前 i 个、末尾颜色是 j 、已经确定位置的颜色集合是 s ，即可转移。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int N=,K=,M=(<<)+;

int n,m,a[N],bin[K],dp[][K][M];

class EllysPearls{

  void cz(int &x,int y){if(y<x)x=y;}

public:

  int getMin(int tN, int tM, vector <int> pearls)

  {

    n=tN; m=tM; for(int i=;i<n;i++)a[i+]=pearls[i];

    bin[]=;for(int i=;i<=m;i++)bin[i]=bin[i-]<<;

    memset(dp[],0x3f,sizeof dp[]);

    dp[][][]=; bool u=,v=;

    for(int i=;i<=n;i++,swap(u,v))

      {

    memset(dp[v],0x3f,sizeof dp[v]);

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

      for(int s=;s<bin[m];s++)//[m]not[n]

        {

          int tp=dp[u][j][s]; if(tp>N)continue;

          int d=bin[a[i]-];

          cz(dp[v][j][s],tp+);

          if(!j||j==a[i])

        cz(dp[v][a[i]][s|d],tp);

          if(!(s&d))

        cz(dp[v][a[i]][s|d],tp);

        }

      }

    int ans=N;

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

      for(int s=;s<bin[m];s++)

    cz(ans,dp[u][j][s]);

    return ans;

  }

};

巴特西

2019 TCO Round 1B——[ 状压DP ]

最新文章

热门文章