- 采药
- 2015-03-28 11:19:41 @
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();
}
}
69 条评论
-
Wangkangle LV 4 @ 2020-11-22 11:36:47
您好,为什么要强调您是女生呢
-
2020-11-21 15:48:05@
您好,为什么要强调您是女生呢
-
2020-11-21 10:36:46@
您好,为什么要强调您是女生呢
-
2020-11-19 22:23:18@
您好,为什么要强调您是女生呢
-
2020-10-26 13:25:20@
您好,为什么要强调您是女生呢
-
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-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么,我不太会。回溯应该可以过吧....嗯..我记得这个数据很水的。
学动态规划吧。这种题目学学入门就能解了,挺不错的