【CC-LECOINS】Little Elephant and Colored Coins

Source and Judge

CC-LECOINS
题意:
n种无限个硬币,有价值v和颜色c,然后q次询问能否恰好凑出价值S,无解就-1,否则最大化不同颜色数量
1 ≤ N ≤ 30
1 ≤ Vi ≤ 200000
1 ≤ Ci ≤ 1e9
1 ≤ Q ≤ 200000
1 ≤ S ≤ 1e18

Analysis

请先思考后再展开

这道题其实难度不大,但因为网上题解少+这sb题卡常,花了我一天时间,相当蛋疼
就是那种意识逐渐模糊,到最后都只知道卡stl、对拍什么的,题意都不太记得了……

建议先做bzoj2118墨墨的等式,也就是不考虑这个颜色
那现在这个颜色,显然不能状压,但可以按顺序处理每种颜色,然后考虑一个dp
$f(0/1,cnt,num)$ 表示上一个使用的硬币和当前颜色是否相同,以及颜色总数、当前值(%v1)
这是一个转移取模的无限背包,咋一看无法转移,但其实只有多个环,每个环就非常好dp了

然后接下来就就是无限长的卡常时间了
$O(n^2V+qn)$

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
//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>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
inline void chmin(ll &x,ll y) {x=x<y?x:y;}
const int MAX_N=31,MAX_M=2e5+10;
int n,m,mn;ll f[2][MAX_N][MAX_M];
bool v[MAX_M];int q[MAX_M];
void insert(int num)//多个环无限背包
{
for(int t=0;t<m;t++)
for(int now=0;now<mn;now++)
chmin(f[0][t+1][(now+num)%mn],f[1][t][now]+num);
memset(v,0,sizeof v);
for(int st=0;st<mn;st++) if(!v[st])
{
int tot=1;q[1]=st;v[st]=1;
for(int now=(st+num)%mn;now!=st;now=(now+num)%mn) q[++tot]=now,v[now]=1;
for(int t=0;t<=m;t++)
{
ll mi=f[0][t][st]-num;
for(int i=2;i<=tot;i++) chmin(f[0][t][q[i]],(ll)num*i+mi),chmin(mi,-(ll)num*i+f[0][t][q[i]]);
for(int i=1;i<=tot;i++) chmin(f[0][t][q[i]],(ll)num*(tot+i)+mi);
}
}
}
pr c[MAX_N];map<int,int> tmp;vector<int> coin[MAX_N];
void main()
{
n=qread(),m=0,mn=INF;
for(int i=1;i<=n;i++)
{
c[i].SE=qread();mn=min(mn,c[i].SE);
int col=qread();if(!tmp.count(col)) tmp[col]=++m;
c[i].FR=tmp[col];
}
sort(c+1,c+n+1);for(int i=1;i<=n;i++) coin[c[i].FR].push_back(c[i].SE);
bool bk=1;//强行放最后
for(int i=1;i<=m;i++)
for(int t=0;t<(int)coin[i].size();t++) if(bk and coin[i][t]==mn)
{swap(coin[i],coin[m+1]);bk=0;break;}
memset(f,0x3f,sizeof f);f[1][0][0]=0;
for(int i=1;i<=m+1;i++)
{
for(int j=0;j<i;j++) for(int t=0;t<mn;t++) chmin(f[1][j][t],f[0][j][t]);
for(int t=0;t<(int)coin[i].size();t++) insert(coin[i][t]);
}
int q=qread();
while(q--)
{
ll wt=qread();
int ans=-1;
for(int lst=0;lst<=1;lst++) for(int t=1;t<=m;t++)
{
ll tmp=f[lst][t][wt%mn];if(tmp>wt) continue;
ans=max(ans,t+(tmp+mn<=wt?lst:0));
}
writeln(ans);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

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