D. Jongmah(永远也想不出来的dp系列)

  • 2019-02-08
  • 0
  • 0

题目链接:https://codeforces.com/contest/1110/problem/D

题意:n个数,可以组成两种三元组(i,i,i)和(i,i+1,i+2),输出n个数最多可以组成多少个三元组。

思路:如果连续3个数大于3个的话,两种三元组的个数是等价的,例如1,1,1,2,2,2,3,3,3,组成111 222 333 与 3个123是等价的,所以规定等价的时候组成(i,i,i),也就是说(i,i+1,i+2)不会超过两个。
dp[i][j][k]代表组成j个以i+1结尾的(i-1,i,i+1)和k个以i+2结尾的(i,i+1,i+2)的时候前i个数最多可以组成多少个。

   i-1   i   i+1   i+2
       dp[i] [y]   [z]
 dp[i-1] [x] [y]

dp[i][y][z]由dp[i-1][x][y]转移而来。

dp[i][y][z]=max(dp[i][y][z],dp[i-1][x][y] + z(新多出来的z个(i,i+1,i+2)) + (i-x-y-z)/3(剩下的i可以组成多少个(i,i,i)))

代码:

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll a[1000005],dp[1000005][3][3];

int main()
{
    ll n,m;
    cin>>n>>m;
    for(ll i=1; i<=n; i++)
    {
        ll x;
        cin>>x;
        a[x]++;
    }
    for(ll i=1; i<=m; i++)
    {
        for(ll x=0; x<3; x++)
        {
            for(ll y=0; y<3; y++)
            {
                for(ll z=0; z<3; z++)
                {
                    if(x+y+z>a[i])continue;
                    dp[i][y][z]=max(dp[i][y][z],dp[i-1][x][y]+z+(a[i]-x-y-z)/3);
                }
            }
        }
    }
    cout<<dp[m][0][0]<<endl;
    return 0;
}

评论

还没有任何评论,你来说两句吧