【CF1110D】Jongmah

Source and Judge

CF1110D

Record

1h

Analysis

请先思考后再展开

一开始有些东西没想清楚就写,太菜了
我写的是dp,然后比较无脑地记录了3个位置,然后当时觉得可以贪心到6以内3以上
然后一直wa,只能过样例,但自己又举不出反例……当时曾经有缩小贪心范围的想法,但又觉得肯定没用就没有尝试……
赛后看看别人的代码感觉差不多,就是上界不一样

那么认真想想,就是x,x+1,x+2最多2次,那么每个位置我们至少需要保留6
所以只要不减少到6及以内,就贪心
具体dp的话状态可以设两维的,但cf比较快就无脑3维了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
// #define pr pair<int,int>
// #define FR first
// #define SE second
// #define MP make_pair
int f[2][10][10][10];
int now[1100000];
void chmax(int &x,int y) {x=x>y?x:y;}
void main()
{
int n,m;scanf("%d%d",&n,&m);
int ans=0;
for(int i=1;i<=n;i++)
{
int a;scanf("%d",&a);
now[a]++;
if(now[a]>=9) now[a]-=3,ans++;
}
if(m>=3)
{
int tmp=0;
memset(f,-63,sizeof f);
f[0][0][now[1]][now[2]]=0;
for(int i=3;i<=m;i++)
{
memset(f[i&1],-63,sizeof f[i&1]);
for(int a=8;a>=0;a--) for(int b=8;b>=0;b--) for(int c=8;c>=0;c--)
{
if(c==now[i])
{
for(int t=0;t<=8;t++) chmax(f[i&1][a][b][c],f[(i-1)&1][t][a][b]);
}
if(f[i&1][a][b][c]<0) continue;
if(a>=1 and b>=1 and c>=1) chmax(f[i&1][a-1][b-1][c-1],f[i&1][a][b][c]+1);
if(a>=3) chmax(f[i&1][a-3][b][c],f[i&1][a][b][c]+1);
if(b>=3) chmax(f[i&1][a][b-3][c],f[i&1][a][b][c]+1);
if(c>=3) chmax(f[i&1][a][b][c-3],f[i&1][a][b][c]+1);
// printf("f[%d][%d][%d][%d]=%d\n",i,a,b,c,f[i&1][a][b][c]);
chmax(tmp,f[i&1][a][b][c]);
}
}
ans+=tmp;
}
else
{
while(now[1]>=3) now[1]-=3,ans++;
while(now[2]>=3) now[2]-=3,ans++;
}
printf("%d",ans);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/5fd7.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%