/ Vijos / 题库 / 养猪 /

题解

11 条题解

  • 3
    @ 2018-11-04 21:15:15
    //首先可以想到一个贪心,如果我们已经确定了要杀哪些猪,那么一定要先杀p比较大的
    //这样我们可以p为第一关键字,a为第二关键字排序
    //之后dp[i][j]表示前i头里杀了j头
    //不断更新就可以了
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    struct node{
        int a,p;
    }q[1010];
    int cmp(const node&x,const node&y)
    {
        if(x.p!=y.p)
         return x.p>y.p;
        return x.a>y.a;
    }
    int dp[1010][1010];
    int main()
    {
        int n,i,j,k,ans=0;
        scanf("%d%d",&n,&k);
        if(k>n)
         k=n;
        for(i=1;i<=n;i++)
         scanf("%d",&q[i].a);
        for(i=1;i<=n;i++)
         scanf("%d",&q[i].p);
        sort(q+1,q+n+1,cmp);
        for(i=1;i<=n;i++)
         for(j=1;j<=k;j++)
          if(q[i].a-(j-1)*q[i].p>0)
           {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+q[i].a-(j-1)*q[i].p);
                ans=max(ans,dp[i][j]);
           }
        printf("%d",ans);
        return 0;
    }
    
  • 0
    @ 2016-08-22 15:02:33

    思路楼下williamchen大神
    ```
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn = 1000 + 5;
    const int INF = 1000000000;

    struct Pig{
    int a, b;
    bool operator < (const Pig& rhs) const {
    return b > rhs.b;
    }
    }p[maxn];

    int n, K;
    int d[maxn][maxn]; //d[i]:第i天杀垮价第j快的猪 i天内最大获益

    void init(){
    cin >> n >> K;
    for (int i = 0; i < n; i++) scanf("%d", &p[i].a);
    for (int i = 0; i < n; i++) scanf("%d", &p[i].b);
    sort(p, p+n);
    memset(d, -1, sizeof(d));
    }

    int dp (int i, int j) {
    if (i > K||j >= n) return 0;
    int& ans = d[i][j];
    if (ans > -1) return ans;
    int x = p[j].a - p[j].b*i;
    if (x < 0) x = 0;
    ans = max(dp(i+1, j+1) + x, dp(i, j+1));
    return ans;
    }

    int main(){
    freopen ( "in.txt" , "r" , stdin);
    init();
    cout << dp(0, 0);
    return 0;
    }
    ```

  • 0
    @ 2015-09-08 16:23:16

    f[i,j]:=max(f[i-1,j],f[i-1,j-1]+max(a[i]-b[i]*(j-1),0));

  • 0
    @ 2013-12-01 19:32:00

    这题跟1574一样。一个程序刷两题。。

  • 0
    @ 2013-10-02 23:32:44

    我从来没见过这么坑的题,害我WA了2次;DP倒是挺水,通过率这么低有以下几个原因
    首先:题目里说是在K天以“内”啊,不一定要是K,但k越大不是更好吗,又不加负数的;至今仍跪求解释(我由10-100);
    其次:A[I]减的应该是p【i】*(j-1),我打成(i-1)了,手误(我由0-10);
    其次:题目里那个?其实是“价值》=0”,负数就算0!!!;
    还有一些是在10-100期间徘徊的我,不断测样例发现错误的
    1:应该要多关键快排,p相等时,A大还要排在前面,以下是自编样例:
    3 3
    14 12 13
    9 7 7
    不双排序,则是14+(12-7)+max(13-7*2,0)=19
    而最优解是14+(13-7)+max(12-7*2,0)=20;
    现在是给下水DP的思路:1.由题目可知p大的一定先杀,n=k时,显然因为都是总的价值-p【1】-p【2】*2-p【3】*3。。。可见前面越大总减得越小(即越优)。2.然后再思考,n比k大时,应该怎么办?因为a谁大并不知道,而杀的顺序一定是按照排玩序的来,无论k是多少;所以问题就变成在一些数中,任意选k个组成最优值(组合);比如编号1,2,3,4,5有5个数,k=3时,可以1-2-3,1-2-4,3-4-5,2-4-5等5C3种组合中取最大的。
    所以DP就特水:每个地方有2种情况,取与不取,即
    f【i,j】:=max(f[i-1,j],f[i-1,j-1]+(a,p);
    L.G.S-庆祝国庆节

  • 0
    @ 2013-08-27 16:19:53

    对于N=K的情况我们发现,因为总和相同,只要按P[i]从大到小杀就可以了,这样损失最小
    那么K>N时
    选出的猪也一定满足P[I]从大到小,所以DP的顺序就出来了
    先把P[i]排序
    第K天杀或不杀第I头猪的最大收益
    F[I,K]=max(f[I-1,K],F[I-1,K-1]+A[I,K])

  • 0
    @ 2013-08-19 18:46:31

    把p[i]排序....再决绝k天后挂掉的猪...

  • 0
    @ 2013-08-19 17:43:49

    略微有种果断贪心的感觉...

  • 0
    @ 2013-05-10 22:16:55

    沙发

  • 0
    @ 2013-03-11 20:57:22

    ##怎么做啊!!!!##

  • 0
    @ 2013-03-10 15:11:49

    这题目~~~略叼

  • 1

信息

ID
1793
难度
7
分类
动态规划 点击显示
标签
(无)
递交数
445
已通过
97
通过率
22%
被复制
2
上传者