专栏首页mathor2017百度之星资格赛:1004. 度度熊的午饭时光

2017百度之星资格赛:1004. 度度熊的午饭时光

题目链接:HDOJ6083

package baidu;
import java.util.*;
public class Main {
    static int B;//预算
    static int N;//菜品数量
    static int[] value = new int[1002];//菜品得分
    static int[] money = new int[1002];//菜品价格
    static int[][] result = new int[101][1002];
    static int[] sta = new int[120];
    static int top = 0,ans = 0;
    static void print(int i,int wt) {
        if(i == 1) {
            if(result[i][wt] != 0) {
                sta[top++] = 1;
                ans += money[1];
            }
            return;
        }
        if(result[i][wt] > result[i - 1][wt]) {
            print(i - 1,wt - money[i]);
            sta[top++] = i;
            ans += money[i];//如果选了,则打印编号
        } 
        else 
            print(i - 1,wt);
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int t = cin.nextInt();
        int sum = 0;
        while((t--) != 0) {
            for(int i = 0;i < 101;i++)
                for(int j = 0;j < 1002;j++)
                    result[i][j] = 0;
            top = ans = 0;
            B = cin.nextInt();
            N = cin.nextInt();
            for(int i = 1;i <= N;i++) {
                value[i] = cin.nextInt();
                money[i] = cin.nextInt();
            }
            for(int i = 1;i <= N;i++) {
                for(int j = 0;j <= B;j++) {
                    if(j < money[i])
                        result[i][j] = result[i - 1][j];
                    else
                        result[i][j] = 
                        Math.max(result[i - 1][j],result[i - 1][j - money[i]] + value[i]);
                }
            }
            if(N != 0)
                print(N,B);
            System.out.println("Case #" + ++sum + ":");
            System.out.print(result[N][B] + " ");
            System.out.println(ans);
            if(0 < top)
                System.out.print(sta[0]);
            for(int i = 1; i < top; ++i)
                    System.out.print(" " +sta[i]);
            if(top > 0)
                System.out.println("");
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2018年全国多校算法寒假训练营练习比赛(第一场)六子冲

     棋盘上攻击方的2个棋子(2子必须相连并主动移动其中的1个)与被攻方的1个棋子皆处在一条直线上并相邻时,被攻方的这个棋子就被消灭  每次移动后判断一下,移动后...

    mathor
  • LeetCode329. 矩阵中的最长递增路径

     dfs,主函数中枚举起点,然后dfs函数中枚举四个方向进行移动,但是光dfs还不够,因为我们发现存在很多冗余,所以这是一道dfs+dp的问题,resul...

    mathor
  • CodeForces D.Powerful array(Div.1)

     大意是是说,问区间[L,R]内的的一个值,这个值是arr[x]出现次数cnt[arr[x]]^2^*arr[x]  这道题Java版的莫队怎么都tle,...

    mathor
  • LeetCode 210. Course Schedule II(拓扑排序)

    和这道题目一样:https://www.cnblogs.com/dacc123/p/12306344.html

    ShenduCC
  • android自定义Toast设定显示时间

    开发android的同学可能会抱怨Toast设定显示的时长无效,只能是Toast.LENGTH_LONG 或者Toast.LENGTH_SHORT 之一,为了解...

    砸漏
  • L3-003. 社交集群

    在社交网络平台注册时,用户通常会输入自己的兴趣爱好,以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序,找出所有的集群。

    指点
  • 哈希算法在判定树同构方面的应用(上)

    树的重心: 找到一个点 , 以点 为根时,其所有的子树中最大的子树节点数最少,那么这个点 就是这棵树的重心。(以重心为根时,最大子树最小)

    ACM算法日常
  • 图论--双连通E-DCC缩点模板

    风骨散人Chiam
  • BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊(LCT)

    attack
  • *(int*)&p

    分析: void(p)(); 这行代码定义了一个指针变量p,p指向一个函数。这个函数的参数和返回值都为void。 &p是求指针变量p本身的地址。 ...

    Daotin

扫码关注云+社区

领取腾讯云代金券