CF730F. Ber Patio
Solution
由于
∑
a
i
\sum{a_i}
∑ai只有
1
0
5
10^5
105，即除掉原有的
b
b
b，代金券最多为
1
0
4
10^4
104，因此我们令
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示到了第
i
i
i天，靠现金获得的代金券共为
j
j
j的最小现金和。
转移时枚举第
i
+
1
i+1
i+1天用
k
k
k张代金券，其他用现金的方法支付：
u
p
m
i
n
(
f
[
i
+
1
]
[
j
+
(
a
[
i
+
1
]
−
k
)
/
10
]
,
f
[
i
]
[
j
]
+
(
a
[
i
+
1
]
−
k
)
)
upmin(f[i+1][j+(a[i+1]-k)/10],f[i][j]+(a[i+1]-k))
upmin(f[i+1][j+(a[i+1]−k)/10],f[i][j]+(a[i+1]−k)) 显然
k
k
k最大不超过
m
i
n
(
a
i
2
,
b
−
(
s
[
i
]
−
f
[
i
]
[
j
]
)
+
j
)
min(\frac{a_i}{2},b-(s[i]-f[i][j])+j)
min(2ai,b−(s[i]−f[i][j])+j)，能在
3
s
3s
3s内解决问题。
Code
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second
#define int ll
using namespace std
;
template<typename T
>inline bool upmin(T
&x
,T y
) { return y
<x
?x
=y
,1:0; }
template<typename T
>inline bool upmax(T
&x
,T y
) { return x
<y
?x
=y
,1:0; }
typedef long long ll
;
typedef unsigned long long ull
;
typedef long double lod
;
typedef pair
<int,int> PR
;
typedef vector
<int> VI
;
const lod eps
=1e-11;
const lod pi
=acos(-1);
const int oo
=1<<30;
const ll loo
=1ll<<62;
const int mods
=998244353;
const int MAXN
=300005;
const int INF
=0x3f3f3f3f;
inline int read()
{
int f
=1,x
=0; char c
=getchar();
while (c
<'0'||c
>'9') { if (c
=='-') f
=-1; c
=getchar(); }
while (c
>='0'&&c
<='9') { x
=(x
<<3)+(x
<<1)+(c
^48); c
=getchar(); }
return x
*f
;
}
vector
<int> Ans
;
int sum
=0,f
[2][10005],a
[5005],s
[5005],frm
[5005][10005];
signed main()
{
int n
=read(),b
=read();
for (int i
=1;i
<=n
;i
++) s
[i
]=s
[i
-1]+(a
[i
]=read());
for (int i
=0;i
<=1;i
++)
for (int j
=0;j
<=s
[n
]/10;j
++) f
[i
][j
]=INF
;
f
[0][0]=0;
int nw
=0;
for (int i
=0;i
<n
;i
++)
{
nw
^=1;
for (int j
=0;j
<=s
[i
]/10;j
++) f
[nw
][j
]=INF
;
for (int j
=0;j
<=s
[i
]/10;j
++)
for (int k
=0;k
<=min(a
[i
+1]/2,b
-(s
[i
]-f
[nw
^1][j
])+j
);k
++)
if (upmin(f
[nw
][j
+(a
[i
+1]-k
)/10],f
[nw
^1][j
]+a
[i
+1]-k
)) frm
[i
+1][j
+(a
[i
+1]-k
)/10]=k
;
}
int ans
=INF
,Nw
=0;
for (int i
=0;i
<=s
[n
]/10;i
++) if (upmin(ans
,f
[nw
][i
])) Nw
=i
;
printf("%lld\n",ans
);
for (int i
=n
;i
>=1;i
--) Ans
.PB(frm
[i
][Nw
]),Nw
=Nw
-((a
[i
]-frm
[i
][Nw
])/10);
for (int i
=n
-1;i
>=0;i
--) printf("%lld ",Ans
[i
]);
return 0;
}
