【动态规划】sicily1221

 

1221. 数字游戏

解题思路：

题目有个地方，我理解错了，导致WA很多次，问题是当你擦除a[i]时，你要将它对应的b[i]去减剩余的序列，之前一直以为第i轮就减去b[i]，ORZ。

简单的动态，dp[i]表示去到第i轮时的最大擦出和。

按照我们直观的思路，肯定是最大消费的（也就是b[i]比较大的）应该先拿掉，因此我们先按照cost排序。

dp[j] = min{dp[j-1] + nodes[i].v - nodes[i].cost*(j-1)};

 

源码如下：

/*
 * main.cpp
 *
 *  Created on: Sep 23, 2011
 *      Author: raphealguo
 */
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXL 210

struct Node{
    int value;
    int cost;
};

bool cmp(Node a, Node b){
    return a.cost > b.cost;
}

int main(){
    int n, m;
    Node nodes[MAXL];
    int i, j;
    int dp[MAXL];

    while (scanf("%d %d", &n, &m) != EOF){
        memset(nodes, 0, sizeof(nodes));
        memset(dp, 0, sizeof(dp));

        for (i = 0; i < n; ++i){
            scanf("%d", &nodes[i].value);
        }
        for (i = 0; i < n; ++i){
            scanf("%d", &nodes[i].cost);
        }
        sort(nodes, nodes+n, cmp);

        for (i = 0; i < n; ++i){
            for (j = m; j >= 1; --j){
                if (dp[j] < dp[j-1] + nodes[i].value - nodes[i].cost*(j-1)){
                    dp[j] = dp[j-1] + nodes[i].value - nodes[i].cost*(j-1);
                }
            }
        }

        printf("%d\n", dp[m]);
    }
}

 

 

附带原题：

1221. 数字游戏

Description

小 W 发明了一个游戏，他在黑板上写出了一行数字 a1,a2,….an ，然后给你 m 个回合的机会，每回合你可以从中选择一个数擦去它，接着剩下来的每个数字 ai 都要递减一个值 bi 。如此重复 m 个回合，所有你擦去的数字之和就是你所得到的分数。  

 小 W 和他的好朋友小 Y 玩了这个游戏，可是他发现，对于每个给出的 an 和 bn 序列，小 Y 的得分总是比他高，所以他就很不服气。于是他想让你帮他算算，对于每个 an 和 bn 序列，可以得到的最大得分是多少。这样他就知道有没有可能超过小 Y 的得分。  

Input

第一行，一个整数 n （ 1<=n<=200 ），表示数字的个数。

第二行，一个整数 m （ 1<=m<=n ），表示回合数。

接下来一行有 n 个不超过 10000 的正整数， a1,a2…an ，表示原始数字

最后一行有 n 个不超过 500 的正整数， b1,b2….bn ，表示每回合每个数字递减的值

Output

一个整数，表示最大可能的得分

Sample Input

3 
3
10 20 30
4 5 6

Sample Output

47

Problem Source

ZSUACM Team Member