CF417A 题解

· · 题解

算法分析：

这是一道背包题。

题意理解：

  1. 需要 n \times m 个选手进入比赛，有 k 人保送。

  2. 淘汰赛分两种比赛。

  3. 正常赛，选拔 n 人，需要 c 道题目。

  4. 特殊赛，选拔 1 人，需要 d 道题目。

目标：最少 需要多少道题目。

解题思路：

  1. 只需要选拔 n\times m - k 人。

  2. 把两种比赛视为背包问题中的两种物品。

  4. 背包的容量：人。

  5. 物品的重量：比赛选拔的人数；物品的价值：比赛的题数。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k,c,d,w[5],dp[10205],val[5];
int main()
{
    cin>>c>>d>>n>>m>>k;//c,d 需要的题目数量，n*m个人，k保送的人数
    w[1]=n; //正常赛 
    val[1]=c;
    w[2]=1;//特殊赛 
    val[2]=d;
    for(int i=1;i<=10200;i++)
        dp[i]=1e9;
    dp[0]=0;//选拔 0 个人，最少0道题目
    for(int i=1;i<=2;i++)//2种物品,即普通赛和特殊赛。
        for(int j=w[i];j<=10200;j++)
            dp[j]=min(dp[j],dp[j-w[i]]+val[i]);
    int ans=1e9;
    for(int i=n*m-k;i<=10200;i++)//取最小值
        ans=min(ans,dp[i]);
    cout<<ans<<endl; 
    return 0; 
}