P8162 题解

Wangxun · 2022-11-13 17:14:15 · 题解

容易想到一个错误的贪心：

• 一定要先得到支持者，再和支持者一起演讲。

• 集中力量办事效率高，支持者们和本人一定要在同一个州进行演讲。

• 按 b_i 从小到大排序，再将剩下的按 a_i 从小到大排序，算出最小值。

但这个贪心有一个问题：可能一些选中的 b_i 对应的 a_i 极其地小。

明确一个问题，我们不选 b_i 的原因是因为 a_i 更加优秀。

我们修改贪心策略，需要加入一些动态规划：

• 按 b_i 从小到大排序。

• 枚举 i,对于前 i 个，肯定是要么选 a_i，要么选 b_i，后面的肯定选 a_i 最小的 k-i 个。

代码也就呼之欲出了：

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(register T &x)
{
    register T p = 1,num = 0;
    char c = getchar();
    while(c < '0'||c > '9')
    {
        if(c == '-') p = -1;
        c = getchar();
    }
    while('0' <= c&&c <= '9')
    {
        num = (num<<3)+(num<<1)+(c^48);
        c = getchar();
    }
    x = p * num;
}
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define D(i,a,b) for(register int i=a;i>=b;--i)
#define N 510
struct node
{
    double a,b;
    inline bool friend operator<(node X,node Y)
    {
        return X.b < Y.b;
    }
}p[N],q[N];
double dp[N][N],sum[N][N];
inline bool cmp(node X,node Y)
{
    return X.a < Y.a;
}
int n,k;
int main()
{
    read(n),read(k);
    F(i,1,n) 
    {
        scanf("%lf%lf",&p[i].a,&p[i].b);
        if(p[i].b == -1) p[i].b = 1e18; 
    }
    sort(&p[1],&p[n+1]); 
    D(i,n,1)
    {
        F(i,1,n) q[i] = p[i];
        sort(&q[i],&q[n+1],cmp);
        F(j,1,n-i+1) sum[i][j] = sum[i][j-1] + q[i+j-1].a;
    } 
    double ans = 1e18;
    F(cas,0,n)
    {
        memset(dp,0x7f,sizeof(dp)); 
        dp[0][0] = 0.0;
        F(i,1,n)
            F(j,0,cas)
            {
                dp[i][j] = min(dp[i][j],dp[i-1][j] + p[i].a / (cas + 1));
                if(j&&p[i].b != 1e18) dp[i][j] = min(dp[i][j],dp[i-1][j-1] + p[i].b / j);   
            }
        F(i,cas,n) ans = min(ans,dp[i][cas] + sum[i+1][k-i] / (cas + 1));
    }
    printf("%.15lf",ans);
    return 0;
}