/ Vijos / 讨论 / 采药 /

我是女生,刚学,搜索写的没有超时,但是wa了,有人能看看吗

package yrh;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class Yrh2 
    {
        public static int n = 0, t_max = 0;
        public static int [] f = new int [11111],t = new int [1111], value = new int [1111];
        public static int ans = -1;
        
        public static void init()
        {
            Scanner sc = new Scanner(System.in);
            t_max = sc.nextInt();
            n = sc.nextInt();
            int [] f = new int [11111];
            int ans = -1;
            Arrays.fill(f, -1);
            f[0] = 0;
            for (int i = 1; i <= n; i++)
            {
                int t = sc.nextInt(),value = sc.nextInt(),j = 0;
                for (j = t_max; j >= t; j--)
                    if (f[j] < f[j-t] + value)
                    {
                        f[j] = f[j-t] + value;
                        if (ans < f[j])
                            ans = f[j];
                    }
            }
            System.out.print(ans);
        }
        
        public static void dfs(int pre, int t_now, int value_now)
        {
            int i = 0;
            f[t_now] = value_now;
            for (i = pre; i <= n; i++)
            {
                if ((t_now + t[i] <= t_max)&&(f[t_now + t[i]] < f[t_now] + value[i]))
                {
                    dfs(i + 1,t_now + t[i],f[t_now] + value[i]);
                }
            }
        }
        public static void Memory_search()
        {
            Scanner sc = new Scanner(System.in);
            t_max = sc.nextInt();
            n = sc.nextInt();
            Arrays.fill(f, -1);
            f[0] = 0;
            for (int i = 1; i <= n; i++)
            {
                t[i] = sc.nextInt();
                value[i] = sc.nextInt();
            }
            dfs(1,0,0);
            for (int i = t_max; i >= 0; i--)
                if (ans < f[i])
                    ans = f[i];
            System.out.print(ans);
        }
        public static void main(String[] arg0)
        {
        //  init();
            Memory_search();
        }
    }

65 条评论

  • @ 2018-01-27 15:24:47

    装逼,你的个人资料里面显示你的性别是男的,但你在这里说你是女生,是不是再什么时候变性了,或者是要打男生打了个女生,但是,反正是一点,你为什么要强调你是女生呢,不怕“装逼遭雷劈,从头到尾劈到……………………………………”,我还要去解题呢,别来烦我!懒得跟你们这种人讲话,真是费劲,唉!你是不是在“打飞机”…………“抱抱亲”呢,哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
    KO
    爆你菊花

  • @ 2018-01-25 19:21:38

    您好,为什么要强调您是女生呢

  • @ 2018-01-25 13:24:54

    您好,为什么要强调您是女生呢

  • @ 2018-01-24 22:35:18

    您好,为什么要强调您是女生呢

  • @ 2018-01-24 18:36:30

    您好,为什么要强调您是女生呢

  • @ 2018-01-17 18:47:56

    您好,为什么要强调您是女生呢

  • @ 2018-01-17 08:15:02

    您好,为什么要强调您是女生呢

  • @ 2018-01-16 16:42:57

    您好,为什么要强调您是女生呢

  • @ 2017-12-31 12:59:50

    您好,为什么要强调您是女生呢

  • @ 2017-12-21 20:14:28

    您好,为什么要强调您是女生呢

  • @ 2017-12-21 13:30:43

    您好,为什么要强调您是女生呢

  • @ 2017-12-16 13:40:27

    您好,为什么要强调您是女生呢

  • @ 2017-12-15 20:09:26

    您好,为什么要强调您是女生呢

  • @ 2016-10-19 21:42:54

    您好,为什么要强调您是女生呢(问一下,这是C++吗)

    • @ 2016-10-24 18:33:22

      这是Java(虽然我只懂C++)

  • @ 2016-10-11 19:16:14

    您好,为什么要强调您是女生呢

  • @ 2016-10-09 11:18:18

    您好,为什么要强调您是女生呢

  • @ 2016-10-05 20:28:50

    您好,为什么要强调您是女生呢

  • @ 2016-10-04 21:52:23

    您好,为什么要强调您是女生呢

  • @ 2016-09-07 19:26:03

    您好,为什么要强调您是女生呢

  • @ 2016-08-27 19:19:11

    您好,为什么要强调您是女生呢

  • @ 2016-08-27 18:07:42

    您好,为什么要强调您是女生呢

  • @ 2016-08-27 11:04:28

    您好,为什么要强调您是女生呢

  • @ 2016-08-03 14:04:22

    您好,为什么要强调您是女生呢

  • @ 2016-07-08 15:16:39

    您好,为什么要强调您是女生呢

  • @ 2016-07-08 15:15:35

    您好,为什么要强调您是女生呢

  • @ 2016-05-29 21:56:31

    您好,为什么要强调您是女生呢

  • @ 2016-05-27 20:58:54

    您好,为什么要强调您是女生呢

  • @ 2016-05-19 16:29:40

    您好,为什么要强调您是女生呢

  • @ 2016-05-09 22:03:27

    您好,为什么要强调您是女生呢(大家一起来刷屏吧)

  • @ 2016-03-25 12:54:09

    您好,为什么要强调您是女生呢

  • @ 2016-03-20 10:21:51

    您好,为什么要强调您是女生呢

  • @ 2016-01-27 10:50:28

    您好,为什么要强调您是女生呢

  • @ 2015-11-01 21:13:23

    您好,为什么要强调您是女生呢

  • @ 2015-10-22 16:26:48

    您好,为什么要强调您是女生呢

  • @ 2015-10-21 16:40:34

    您好,为什么要强调您是女生呢

  • @ 2015-09-07 18:51:33

    你的错误很明显

  • @ 2015-08-16 17:26:37

    您好,为什么要强调您是女生呢

  • @ 2015-08-04 11:38:39

    女生。。。。。。

  • @ 2015-06-03 16:52:04

    为什么要强调你是女生呢?

  • @ 2015-06-03 16:51:30

    女生。。。。。。。。

  • @ 2015-05-27 19:19:25

    您好,为什么要强调您是女生呢

  • @ 2015-05-26 13:01:27

    您好,为什么要强调您是女生呢

  • @ 2015-05-25 19:03:57

    ....

  • @ 2015-05-24 01:05:27

    您好,为什么要强调您是女生呢(我也来水楼……)

  • @ 2015-04-24 21:17:57

    醉了。。。

  • @ 2015-04-18 12:57:47

    java么,我不太会。回溯应该可以过吧....嗯..我记得这个数据很水的。

    学动态规划吧。这种题目学学入门就能解了,挺不错的

  • @ 2015-04-16 19:40:17

    刚学?你5年前注册的号??!!

  • @ 2015-04-16 19:37:40

    半年不来vijos了,今天来签个到

  • @ 2015-04-16 19:32:55

    非记忆化搜索不可能过的,死心吧

  • @ 2015-04-16 19:31:25

    您好,为什么要强调您是女生呢

信息

ID
1104
难度
4
分类
动态规划 | 背包 点击显示
标签
递交数
15484
已通过
6058
通过率
39%
上传者