总结
比较经典的题型，小范围内的DP通常会转化为图论
小红不想做完全背包 （hard）
地址
对于每一个物品，可以产生 p 条路径：$0$->$a[i]$%p,$1$->$(a[i]+1)$%p$…$$p-1$->$(a[i]+p-1)$%p
然后利用 BFS 求出到 0 的最短路，每一个 a[i] 都是起始点
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
| void solve()
{
int n,p;
cin>>n>>p;
queue<int> q;
for(int i=0;i<=p;i++) d[i]=INF;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]%=p;
if(d[a[i]]!=1){
q.push(a[i]);
for(int j=0;j<p;j++){
g[j].push_back((j+a[i])%p);
}
}
d[a[i]]=1;
}
while(!q.empty()){
int u=q.front();q.pop();
for(auto v : g[u]){
if(d[v]==INF){
d[v]=d[u]+1;
q.push(v);
}
}
}
cout<<d[0];
}
|
Tokitsukaze and Slash Draw
地址
同样因为取模的特性，导致点的大小范围事实上较小，可以用 DP ，同样可以转化为图论，利用最短路解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void solve()
{
int n,m,k;
cin>>n>>m>>k;
vector<int> a(m+1),b(m+1);
vector<int> prc(n+1,INF);
for(int i=1;i<=m;i++){
cin>>a[i]>>b[i];
for(int j=1;j<=n;j++){
prc[(a[i]*j-1)%n+1]=min(prc[(a[i]*j-1)%n+1],b[i]*j);
}
}
vector<int> dp(n+1,INF);//dp[i]表示牌在从下往上数第i张时的最小代价
dp[k]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(prc[i]!=INF) dp[j]=min(dp[j],dp[(j-i+n-1)%n+1]+prc[i]);
}
}
cout<<(dp[n]==INF ? -1 : dp[n])<<"\n";
}
|