/ 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();
}
}

60 条评论

  • @ 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-17 21:21:04

      您好 为什么您不一次把话说完呢

    • @ 2015-04-24 19:54:58

      因为

    • @ 2015-04-24 19:55:11

      我刚学

    • @ 2015-04-24 19:55:17

      MD编辑

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

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

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

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

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

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

  • @ 2015-04-15 17:56:09

    什么鬼

  • @ 2015-04-15 17:56:04

    擦。。

  • @ 2015-04-15 17:55:52

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    typedef long long LL;

    struct Change{
    int x , y , z , s1 , s2;
    };

    const int N = 100010;
    Change a1[4 * N] , a2[4 * N];
    LL f[8 * N] , ans;
    int t;

    bool Dox(Change A , Change B){return A.x < B.x;}

    LL Min(LL x , LL y){
    if (x == -1) return y;
    if (y == -1) return x;
    return min(x , y);
    }

    LL Ask(int s , int l , int r , int x , int y){
    if (l == x && r == y) return f[s];
    int mid = (l + r) / 2;
    if (y <= mid) return Ask(s * 2 , l , mid , x , y);
    else if (x > mid) return Ask(s * 2 + 1 , mid + 1 , r , x , y);
    else return Min(Ask(s * 2 , l , mid , x , mid) , Ask(s * 2 + 1 , mid + 1 , r , mid + 1 , y));
    }

    void Putin(int s , int l , int r , int x , LL z){
    if (l == x && r == x){
    f[s] = Min(z , f[s]);
    return;
    }
    int mid = (l + r) / 2;
    if (x <= mid) Putin(s * 2 , l , mid , x , z);
    else Putin(s * 2 + 1 , mid + 1 , r , x , z);
    f[s] = Min(f[s * 2] , f[s * 2 + 1]);
    }

    void Work(){
    int n , m;
    scanf("%d %d" , &n , &m);
    memset(a1 , 0 , sizeof(a1));
    memset(a2 , 0 , sizeof(a2));
    int t = 0;
    for(int i = 1; i <= n; i ++)
    scanf("%d %d %d" , &a1[i].x , &a1[i].y , &a1[i].z);
    if (m == 1){
    ans = 0;
    return;
    }
    sort(a1 + 1 , a1 + 1 + n , Dox);
    for(int i = 1; i <= n; i ++){
    a2[i].x = a1[i].x; a2[i + n].x = a1[i].y;
    a2[i].s1 = i; a2[i].s2 = 1;
    a2[i + n].s1 = i; a2[i + n].s2 = 2;
    }
    sort(a2 + 1 , a2 + 1 + 2 * n , Dox);
    t = 1; int last = 1; bool bb = 1;
    for(int i = 1; i <= 2 * n; i ++){
    if (a2[i].x != last){
    t ++;
    if (bb && a2[i].x >= m){
    bb = 0;
    m = t;
    if (a2[i].x > m) t ++;
    }
    last = a2[i].x;
    }
    if (a2[i].s2 == 1) a1[a2[i].s1].x = t;
    else a1[a2[i].s1].y = t;
    }
    memset(f , 255 , sizeof(f));
    Putin(1 , 1 , t , 1 , 0);
    a1[0].x = 1; ans = -1;
    bb = 1;
    for(int i = 1; i <= n; i ++) if (a1[i].y == 1){
    bb = 0;
    }
    for(int i = 1; i <= n; i ++){
    LL tt = -1;
    if (a1[i - 1].x >= a1[i].y) tt = Ask(1 , 1 , t , a1[i].y , a1[i - 1].x);
    if (tt != -1){
    tt += a1[i].z;
    Putin(1 , 1 , t , a1[i].x , tt);
    if (a1[i].x >= m) ans = Min(ans , tt);
    }
    }
    ans = ans;
    }

    int main(){
    freopen("a.in" , "r" , stdin);
    freopen("a.out" , "w" , stdout);

    scanf("%d" , &t);
    for(int i = 1; i <= t; i ++){
    Work();
    printf("Case #%d: %lld\n" , i , ans);
    }

    return 0;
    }

  • @ 2015-04-15 17:53:28

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

  • @ 2015-04-08 20:24:56

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

信息

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