CF837D

发表于 分类于
Round Subset

Round Subset

Now the only problem of the post is that the sign ' doesn’t render well.

So it is the first time, maybe the last time…

Here I want to try a new form to deliver my post.

You see, I won’t use Chinese in the post. Instead, I’d like to write this blog in English.

The only reason is that I’m very bored…

At first, we can see that if we want to piece together a $10$, the only factor we need are $2$ and $5$.

Apart from these two factors, we can not find any other factors has the ability to piece together $10$.

Since we have the basis thinking, let’s find what is the truly roundness.

If we divide the number $a _ i$ till there is no roundness in it, we can get another number $a ^ {\prime} _ i$.

The number $a ^ {\prime} _ i$ will have a beatiful nature: It doesn’t have factor $2$ and factor $5$ at the same time.

So we might as well define the status $f ( i , j , k )$, which indicates that $j$ numbers have been selected in the previous $i$ numbers, and the products has already had $k$ factors $2$.

Similarly, we define $g ( i , j , k )$, the only difference between them is that the $k$ of $g$ represents the number of $5$.

Now, we can try to write the transform of the state:

$$
f ( i , j , k )
\rightarrow
\begin{cases}
f ( i + 1 , j , k )
\\
f ( i + 1 , j + 1 , k + c _ 2 ( i + 1 ))
\\
f ( i + 1 , j + 1 , k - c _ 5 ( i + 1 ))
\\
g ( i + 1 , j + 1 c _ 5 ( i + 1 ) - k )
\end{cases}
$$

The state $g$ is similar:

$$
g( i , j , k )
\rightarrow
\begin{cases}
g ( i + 1 , j , k )
\\
g ( i + 1 , j + 1 , k + c _ 5 ( i + 1 ))
\\
g ( i + 1 , j + 1 , k - c _ 2 ( i + 1 ))
\\
f ( i + 1 , j + 1 , c _ 2 ( i + 1 ) - k )
\end{cases}
$$

And the time complexity of it is $ O( n ^ 3 \log a) $.

Because the online judge isn’t very stable, it takes me some time to accept the problem…

Code:

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll N=2e2,M=2e4,inf=(1ll<<31)-1;

ll n,K,m2,m5,m;
ll a[N+5],r[N+5],c2[N+5],c5[N+5];
ll f[2][N+5][M+5],g[2][N+5][M+5];

int main() {

  n=read();K=read();

  for(ll i=1;i<=n;i++) {
    a[i]=read();
    while(a[i]%10==0) {a[i]/=10;r[i]++;}
    while(a[i]%2==0) {a[i]/=2;c2[i]++;}
    while(a[i]%5==0) {a[i]/=5;c5[i]++;}
  }

  for(ll j=0;j<=K;j++) {
    for(ll k=0;k<=M;k++) {
      f[0][j][k]=g[0][j][k]=-inf;
      f[1][j][k]=g[1][j][k]=-inf;
    }
  }

  f[0][0][0]=g[0][0][0]=0;

  for(ll i=0;i<n;i++) {
    m2+=c2[i+1];m5+=c5[i+1];
    m=max(m2,m5);
    for(ll j=0;j<=K&&j<=i;j++) {
      for(ll k=0;k<=m;k++) {
        f[(i+1)&1][j][k]=max(f[(i+1)&1][j][k],f[i&1][j][k]);
        if(j+1<=K) {
          if(c2[i+1]) {
            f[(i+1)&1][j+1][k+c2[i+1]]=
            max(f[(i+1)&1][j+1][k+c2[i+1]],f[i&1][j][k]+r[i+1]);
          }
          else {
            if(c5[i+1]<k) {
              f[(i+1)&1][j+1][k-c5[i+1]]=
              max(f[(i+1)&1][j+1][k-c5[i+1]],f[i&1][j][k]+r[i+1]+c5[i+1]);
            }
            else {
              g[(i+1)&1][j+1][c5[i+1]-k]=
              max(g[(i+1)&1][j+1][c5[i+1]-k],f[i&1][j][k]+r[i+1]+k);
            }
            if(c5[i+1]==k) {
              f[(i+1)&1][j+1][0]=
              max(f[(i+1)&1][j+1][0],f[i&1][j][k]+r[i+1]+k);
            }
          }
        }
        g[(i+1)&1][j][k]=max(g[(i+1)&1][j][k],g[i&1][j][k]);
        if(j+1<=K) {
          if(c5[i+1]) {
            g[(i+1)&1][j+1][k+c5[i+1]]=
            max(g[(i+1)&1][j+1][k+c5[i+1]],g[i&1][j][k]+r[i+1]);
          }
          else {
            if(c2[i+1]<k) {
              g[(i+1)&1][j+1][k-c2[i+1]]=
              max(g[(i+1)&1][j+1][k-c2[i+1]],g[i&1][j][k]+r[i+1]+c2[i+1]);
            }
            else {
              f[(i+1)&1][j+1][c2[i+1]-k]=
              max(f[(i+1)&1][j+1][c2[i+1]-k],g[i&1][j][k]+r[i+1]+k);
            }
            if(c2[i+1]==k) {
              g[(i+1)&1][j+1][0]=
              max(g[(i+1)&1][j+1][0],g[i&1][j][k]+r[i+1]+k);
            }
          }
        }
      }
    }
    for(ll j=0;j<=K&&j<=i;j++) {
      for(ll k=0;k<=m;k++) {
        f[i&1][j][k]=g[i&1][j][k]=-inf;
      }
    }
  }

  ll ans=0;
  for(ll k=0;k<=m;k++) {
    ans=max(ans,max(f[n&1][K][k],g[n&1][K][k]));
  }

  write(ans);

  return 0;
}