当前位置:Gxlcms > html代码 > CodeforcesRound#214(Div.2)??DimaandSalad_html/css_WEB-ITnose

CodeforcesRound#214(Div.2)??DimaandSalad_html/css_WEB-ITnose

时间:2021-07-01 10:21:17 帮助过:27人阅读

题目链接

  • 题意:
    一行a[i],一行b[i],a和b是一一对应的。选取任意个数对,使得sigma(a)/ sigma(b)等于k,求这时候sigma(a)的最大值
  • 分析:
    这个题目关键在于对sigma(a)/ sigma(b)== k的处理。对于这种式子,用每个数的比值显然是不行的,因为没法累加;而且是double型,没法DP
    考虑一个每个数对对这个式子的影响,如果每个数都是a = k * b,那么显然是可以的;如果a小于k * b,那么在整体中,当前数对少的数肯定要有一些数对来补偿,也就是说,记x = k * b - a,所有选择的数对的x的和应该是零。
    那么,每个数对其实就变成了一个可正可负的数,求若干个和为零的数的sigma(b)的最大值,正负分开,用背包解决即可
  • const int MAXN = 110;const int M = 210000;int tastes[MAXN], calories[MAXN];int v[MAXN];int dp[2][M];int main(){//    freopen("in.txt", "r", stdin);    int n, m;    while (~RII(n, m))    {        REP(i, n) RI(tastes[i]);        REP(i, n) RI(calories[i]);        REP(i, n) v[i] = tastes[i] - calories[i] * m;        CLR(dp, -INF);        dp[0][0] = dp[1][0] = 0;        REP(i, n)        {            int cnt = v[i] < 0, val = abs(v[i]);            FED(j, M - val - 1, 0)                dp[cnt][j + val] = max(dp[cnt][j + val], dp[cnt][j] + tastes[i]);        }        int ans = 0;        REP(i, M)            ans = max(ans, dp[0][i] + dp[1][i]);        if (ans <= 0)            puts("-1");        else            WI(ans);    }    return 0;}

    人气教程排行