复习背包问题

我的代码只能在无优化开关才能过……

program cc;
var
n,s,i,t,r,k,a,b,c,d,j:longint;
f:array[1..10000000]of int64;
begin
assign(input,'read.in');
assign(output,'read.out');
reset(input);
rewrite(output);
readln(n,k);
for i:=1 to k do
begin
readln(s,t,r);
a:=n div s;
c:=n mod s;
b:=(a div t)*r;
if c=0 then
d:=a+b else d:=a+b+1;
f[i]:=d;
end;
for j:=1 to k do writeln(f[j]);
end.
各位大犇，看看为什么过不了

回复 @TA :
那个标记其实不用管啦……不加优化也可以过的

还是贴一下90分的代码……这个没有考虑“第二阶段中进驻到首都的军队比最初部署到首都的军队更‘无用’”的情况……（太拗口……）
@chs

先用线段树水到85，丧心病狂地用读入优化+静态化搞到90……最后才知道差分序列有这种用法QAQ……果然自己太弱
借自己的楼临时贴一下90分的区间修改+区间查询的线段树…… @chs

丧心病狂的贪心……我会说我差点敲了个分治吗……
好吧其实证明的时候用到了数学归纳的思想……假设前n个都已经盖成，此时若$h_i \geq h_{i+1}$，那么我们只需要在前面覆盖i点时多往后覆盖一格就可以了……但如果$h_i < h_{i+1}$，因为每次只能增加一个积木，而覆盖的区间又必须连续，那么这时我们至少要多进行$h_{i+1} - h_i$次操作= =
然后空间复杂度就可以果断$O(1)$了……

又见五星神题……

kmp算法 详解请看http://blog.sina.com.cn/s/blog_13a7287f40102v4vh.html

我感觉像记忆化搜索？？？？？

单调队列优化DP。 不过数据比较水， O(n^3) 都秒过

回复 @柚子冰 :
尽管数组开得太大导致IDE崩溃无法编译，我还是过了

开bool型爆不了yooooooo

回复 @传奇 :
炫迈........

为什么我的程序超时？到1秒了还停不下来

我什么都不说

每次都忘了ansistring，QAQ~~~~~~

楼上注意题意，不论什么数据，答案至少为1，因为一个数据必满足单调递减。

整齐的代码，我喜欢。。COGS 300T，1500留念。。