Watch The Movie

时间：2022-02-03 15:08:54

Watch The Movie

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)

Total Submission(s): 6661 Accepted Submission(s): 2121

Problem Description

New semester is coming, and DuoDuo has to go to school tomorrow. She decides to have fun tonight and will be very busy after tonight. She like watch cartoon very much. So she wants her uncle to buy some movies and watch with her tonight. Her grandfather gave them L minutes to watch the cartoon. After that they have to go to sleep.

DuoDuo list N piece of movies from 1 to N. All of them are her favorite, and she wants her uncle buy for her. She give a value Vi (Vi > 0) of the N piece of movies. The higher value a movie gets shows that DuoDuo likes it more. Each movie has a time Ti to play over. If a movie DuoDuo choice to watch she won’t stop until it goes to end.

But there is a strange problem, the shop just sell M piece of movies (not less or more then), It is difficult for her uncle to make the decision. How to select M piece of movies from N piece of DVDs that DuoDuo want to get the highest value and the time they cost not more then L.

How clever you are! Please help DuoDuo’s uncle.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by input data for each test case:

The first line is: N(N <= 100),M(M<=N),L(L <= 1000)

N: the number of DVD that DuoDuo want buy.

M: the number of DVD that the shop can sale.

L: the longest time that her grandfather allowed to watch.

The second line to N+1 line, each line contain two numbers. The first number is the time of the ith DVD, and the second number is the value of ith DVD that DuoDuo rated.

Output

Contain one number. (It is less then 2^31.)

The total value that DuoDuo can get tonight.

If DuoDuo can’t watch all of the movies that her uncle had bought for her, please output 0.

Sample Input

1

3 2 10

11 100

1 2

9 1

Sample Output

3

二维费用背包

Dp[i][j][K]表示选第i个电影是花费的总时间为j,看的电影数为k,

所以DP[i][j][k]=max(Dp[i-1][j-Time[i]][k-1]+value[i],Dp[i-1][j][k]);转化为01背包

比较坑的是,价值有负值……无语……

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <queue>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<int,int>p;

const int INF = 0x3f3f3f3f;

int Dp[1100][120];

p movie[120];

int main()

{

    int n,m,L;

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d %d %d",&n,&m,&L);

        for(int i=1;i<=n;i++)

        {

            scanf("%d %d",&movie[i].first,&movie[i].second);

        }

        for(int i=0;i<=L;i++)

        {

            for(int j=0;j<=m;j++)

            {

                if(!j)

                {

                    Dp[i][j]=0;

                }

                else

                {

                    Dp[i][j]=-INF;

                }

            }

        }

        for(int i=1;i<=n;i++)

        {

            for(int j=L;j>=movie[i].first;j--)

            {

                for(int k=1;k<=m;k++)

                {

                    Dp[j][k]=max(Dp[j-movie[i].first][k-1]+movie[i].second,Dp[j][k]);

                }

            }

        }

       if(Dp[L][m]<0)

       {

           Dp[L][m]=0;

       }

        printf("%d\n",Dp[L][m]);

    }

    return 0;

}

随机推荐

  1. Loadrunner11安装和破解方法

    公司很多项目都在做性能测试,打算把性能测试学习下.(不懂还可以问问公司大神,这么好的机会不要错过了O(∩_∩)O哈哈~)用了二周实践看了性能测试方面一些基本术语和概念,一直都还没自己动手实践,光看基本 ...

  2. codeforces 557D&period; Vitaly and Cycle 二分图染色

    题目链接 n个点, m条边, 问最少加几条边可以出现一个奇环, 在这种情况下, 有多少种加边的方式. 具体看代码解释 #include<bits/stdc++.h> using names ...

  3. Laravel nginx 伪静态规则

    最近的各种调查PHP相框(CI, Cake, ThinkPHP, Laravel, Yii)情绪Laravel它看起来很漂亮,下一个深入了解.用发展机Apache,Stage在运行nginx,一旦部署 ...

  4. &lbrack;转&rsqb;从入门到精通&colon; 最小费用流的&OpenCurlyDoubleQuote;zkw算法”

    >>>> 原文地址:最小费用流的“zkw算法” <<<< 1. 网络流的一些基本概念 很多同学建立过网络流模型做题目, 也学过了各种算法, 但是对于基本 ...

  5. 三， 练习 python索引 （list和tuple）

    (1) 练习 请用索引取出下面list的指定元素: 1, # -*- coding: utf-8 -*- L = [ ['Apple', 'Google', 'Microsoft'], ['Java' ...

  6. JQuery未来元素事件监听写法

    $(document).on('click','.div1',function(){ alert("abc"); }); 格式一致,第一个参数写事件,第二个参数给谁写事件(选择器) ...

  7. UVA506-System Dependencies&lpar;拓扑序&rpar;

    Problem UVA506-System Dependencies Accept:285  Submit:2824 Time Limit: 3000 mSec Problem Description ...

  8. tcp的4次挥手、三次握手

    1. TCP短连接模拟一种TCP短连接的情况:1. client 向 server 发起连接请求2. server 接到请求,双⽅建⽴连接3. client 向 server 发送消息4. serve ...

  9. 转&Tab;iOS宏定义的使用与规范

    宏定义在很多方面都会使用,例如定义高度.判断iOS系统.工具类,还有诸如文件路径.服务端api接口文档.为了对宏能够快速定位和了解其功能,我们最好在定义的时候将其放入特定的头文件中,下面我抛砖引玉,对 ...

  10. Python高级特性：迭代器和生成器 -转

    在Python中,很多对象都是可以通过for语句来直接遍历的,例如list.string.dict等等,这些对象都可以被称为可迭代对象.至于说哪些对象是可以被迭代访问的,就要了解一下迭代器相关的知识了 ...

相关文章