总结

比较经典的题型，小范围内的DP通常会转化为图论

小红不想做完全背包 （hard）

地址

对于每一个物品，可以产生 p 条路径：$0$->$a[i]$%p,$1$->$(a[i]+1)$%p...$$p-1->$(a[i]+p-1)$%p

然后利用 BFS 求出到 0 的最短路，每一个 a[i] 都是起始点

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 ，同样可以转化为图论，利用最短路解决

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";
}