请问为什么这个O(n^2)的DP会TLE?数据范围真的是2000内?

P1107 [BJWC2008] 雷涛的小猫

@[PopChicken](/space/show?uid=66215) @ [PopChicken](/space/show?uid=66215) ## 将所有cin,cout换成scanf,printf 亲测可以过 ```cpp #include <iostream> #include <algorithm> #include <cstdio> using namespace std; int d[2010]; int f[2010][2010]; int main() { int N, H, D; scanf("%d %d %d",&N,&H,&D); for (int i = 1; i <= N; i++) { int Ni; scanf("%d",&Ni); for (int j = 1; j <= Ni; j++) { int T; scanf("%d",&T); f[i][T]++; } } for (int h = 1; h <= H; h++) { for (int t = 1; t <= N; t++) { if (h <= D) { f[t][h] += f[t][h - 1]; d[h] = max(d[h], f[t][h]); continue; } f[t][h] += max(d[h - D], f[t][h - 1]); d[h] = max(d[h], f[t][h]); } } printf("%d\n",d[H]); return 0; } ```
by interestingLSY @ 2018-03-27 00:25:46


#1 AC 524ms/17488KB #2 AC 0ms/2187KB
by interestingLSY @ 2018-03-27 00:26:03


@[interestingLSY](/space/show?uid=25630) 嗯嗯谢谢大佬,话说cin比scanf慢多少哇?
by Blazar北极星 @ 2018-03-27 18:32:37


@[PopChicken](/space/show?uid=66215) 慢很多,NOIP中不要用 即使加上 ```cpp ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ``` 也会慢
by interestingLSY @ 2018-03-28 23:18:14


@[interestingLSY](/space/show?uid=25630) 好的,感谢感谢
by Blazar北极星 @ 2018-03-29 12:12:30


@[interestingLSY](/space/show?uid=25630) 这样容易蜜汁RE,CF亲测。。
by sxyugao @ 2018-04-11 18:13:18


@[sxyugao](/space/show?uid=12832) 谢谢dalao!
by interestingLSY @ 2018-04-14 22:13:36


加快读。给你一篇博文:[【洛谷日报#110】浅谈C IO优化——读优输优方法集锦](http://www.360doc.com/content/19/0107/07/5315_807139869.shtml)
by Hadtsti @ 2021-06-29 11:31:20


|