/*
*********************************有一定的钱 存在银行里给出可存的钱数 和相应利息第一年的利息会加入到第二年的本金中**********************************
*/
#include
<
iostream
>
#include
<
stdio.h
>
#include
<
cstring
>
using
namespace
std;
int
d[
50000
],v[
12
],w[
12
];
//
数组开大了会超时
int
main(){
int
n;
//
freopen("out.txt","w",stdout);
scanf(
"
%d
"
,
&
n);
for
(
int
l
=
1
;l
<=
n;l
++
) {
int
c,k;
int
m; scanf(
"
%d %d
"
,
&
c,
&
k); scanf(
"
%d
"
,
&
m);
for
(
int
i
=
1
;i
<=
m;i
++
) { scanf(
"
%d %d
"
,
&
v[i],
&
w[i]); v[i]
/=
1000
; }
while
(k
--
) {
int
t
=
c
/
1000
;
//
因为是1000的倍数 所以 都除以1000 优化一下子
memset(d,
0
,
sizeof
(d));
for
(
int
i
=
1
;i
<=
m;i
++
)
for
(
int
j
=
0
;j
<=
t;j
++
) {
if
(j
>=
v[i])
if
(d[j]
<
(d[j
-
v[i]]
+
w[i])) { d[j]
=
d[j
-
v[i]]
+
w[i]; } } c
=
c
+
d[t]; } printf(
"
%d\n
"
,c); }
return
0
;}
转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048249.html
相关资源：JAVA上百实例源码以及开源项目
