晕~好简单的DP

第一问真的没啥技术含量，第二问请注意hint里的提示就没问题了

为什么是柯哀，

支持新兰

在最后加上一个0，然后就最长下降子序列的尾就统一了啊

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

晕...算方案数时我判重，有个点过不去...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25ms

没想到这么慢…… 没想到没人发程序…… 没想到后面还有个Hint！！！！！！！！

#include

using namespace std;

main()

{

int n,ml;

cin>>n;

int f[3010],p[3010];

memset(f,0,sizeof(f));

memset(p,0,sizeof(p));

long a[3010];

a[0]=2147483647;ml=1;p[0]=1;

for (int i=1;i>a[i];

for (int j=0;ja[i]&&f[i]ml) ml=f[i];

}

int pp=0;

for (int i=1;i

之前是采用删除前面的相同的点,保留最后面的,可是总错,后来看了USACO4.3.1的题解,按那种方法做的,主要的DP没变,居然0MS A了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

恶心.....

额。。比较无语的题目。。朴素秒过。。本来还想改成nlogn的，完全没必要

景仰 一下大葱

在过程中mod 10000是防溢出把，在数学上完全没错的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25ms

使用一般的求最长不下降子序列的nlogn算法是可行的。

设g[i]=所有使f[j]=i的j的集合。

为了能够随时得到g[i]的最大值。我们将g[i]这个集合用最大堆来实现。

这样，求f[i]时就可以二分答案了。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案错误...

├ 标准行输出 5 20

├ 错误行输出 5 36

├ 测试数据 05：答案错误...

├ 标准行输出 36 16

├ 错误行输出 36 30...

├ 测试数据 06：答案错误...程序输出比正确答案长

├ 测试数据 07：答案错误...

├ 标准行输出 59 2224

├ 错误行输出 59 7152

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案错误...程序输出比正确答案长

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：50 有效耗时：41ms

想不通……

第2666次是我交的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 40ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：40ms

├ 测试数据 01：答案正确... -1ms

├ 测试数据 02：答案正确... -1ms

├ 测试数据 03：答案正确... -1ms

├ 测试数据 04：答案正确... -1ms

├ 测试数据 05：答案正确... -1ms

├ 测试数据 06：答案正确... -1ms

├ 测试数据 07：答案正确... -1ms

├ 测试数据 08：答案正确... -1ms

├ 测试数据 09：答案正确... -1ms

├ 测试数据 10：答案正确... -1ms

以前没有写过题解的....

其实 看到这道题的时候 很奇怪他的AC率怎么这么低

..后来发现自己也是4次才秒杀..

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

在计算过程中要mod 10000 虽然我还不知道为什么 ...

第一次..循环少了一次

第二次..没看到要mod 10000

第三次..没注意全部都要mod 10000...看到下面大牛的题解才明..但至今不明为什么要在过程中mod 题目有说吗?

第四次..AC---|-->伐客！！！

这个题的数据实在阴险……

这不是……

纯粹的导弹拦截问题么

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• -
  那我简单说几句,
  LCS谁都会吧...
  计算方案利用加法原理...主要就是判重,我开了个数组纪录相同状况...应该算比较麻烦的算法吧,不过数据小所以时间上没什么那个什么= =|
  就这样...

终于AC了

有些感受不得不说一下

令 A的最常上升高度为f,方案数为C

1.推理时有可能得到C=0，比如第一个数的计算，此时不能C:=1;

因为10000 mod 10000=0，一定要判断是否是超过0了，否则第9点wa

2.方案数推理

i 1 -> n

c[i]:=c[j1]+c[j2]...c[jn],j满足1

最长下降子序列，o(∩_∩)o...，弱！！！