/*
看第一个周期
1~t+1,t+1~2t+1
我们考虑i与i+1的关系，就变成
1~t一组，t~2t一组
因此是(i-1)/t mod 2=0递减，否则递增

代数验证：
[2kt+1,(2k+1)t]这段区间-1为
[2kt,(2k+1)t-1]
再除t向下取整为2k
2k mod 2=0
这段区间递减
递增类似

1　　　　　7　　　　　　　13
　　2　　　6　8　　　　12 ..
　　　3　5　　　9　　11
　　　　4　　　　　10

*/
#include <iostream>
#include <algorithm>
using namespace std;
int dp[2005];
int main()
{
int a[2005],n,k;
cin>>n>>k;;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if((dp[j]+1)%k==0)
{
if((dp[j]+1)/k%2==0)
{
if(a[i]>a[j])
dp[i]=max(dp[j]+1,dp[i]);
}
else
{
if(a[i]<a[j])
dp[i]=max(dp[j]+1,dp[i]);
}
}
else
{
if(((dp[j]+1)/k+1)%2==0)
{
if(a[i]>a[j])
dp[i]=max(dp[j]+1,dp[i]);
}
else
{
if(a[i]<a[j])
dp[i]=max(dp[j]+1,dp[i]);
}
}

}
}
int maxn=0;
for(int i=1;i<=n;i++)
{ maxn=max(dp[i],maxn);
}
cout<<maxn+1<<endl;
return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
int dp[2005];
int main()
{

int a[2005],n,k;
cin>>n>>k;;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}

for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{

if((dp[j]+1)%k==0)
{
if((dp[j]+1)/k%2==0)
{
if(a[i]>a[j])
dp[i]=max(dp[j]+1,dp[i]);
}
else
{
if(a[i]<a[j])
dp[i]=max(dp[j]+1,dp[i]);
}
}
else
{
if(((dp[j]+1)/k+1)%2==0)
{
if(a[i]>a[j])
dp[i]=max(dp[j]+1,dp[i]);
}
else
{
if(a[i]<a[j])
dp[i]=max(dp[j]+1,dp[i]);
}
}

}
}
int maxn=0;
for(int i=1;i<=n;i++)
{ maxn=max(dp[i],maxn);
}
cout<<maxn+1<<endl;
return 0;
} 终于有收获了

O（t*N^2）

program p1686;
var f:array[0..2000,1..21] of longint;
a:array[0..2000] of longint;
i,j,n,t,k,sum:longint;
//
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
//
begin
assign(input,'p1686.in');assign(output,'p1686.out');
reset(input);rewrite(output);
read(n,t);
for i:=1 to n do read(a[i]);for i:=1 to n do f[i,1]:=1;
for i:=1 to n do
begin
for k:=1 to i-1 do if (a[k]<a[i]) and (f[k,2*t]<>0) then f[i,1]:=max(f[i,1],f[k,2*t]+1);
for j:=2 to t+1 do
for k:=1 to i-1 do if (a[k]>a[i]) and (f[k,(j+2*t-1) mod (2*t)]<>0) then f[i,j]:=max(f[k,(j+2*t-1) mod (2*t)],f[i,j]);
for j:=t+2 to 2*t do
for k:=1 to i-1 do if (a[k]<a[i]) and (f[k,(j+2*t-1) mod (2*t)]<>0) then f[i,j]:=max(f[k,(j+2*t-1) mod (2*t)],f[i,j]);
end;
for i:=1 to n do
for j:=1 to 2*t do sum:=max(sum,(f[i,j]-1)*2*t+j);
write(sum);
close(output);
end.

觉得楼下都好牛，写的都是N^2的
我写的是T*N^2
f[i,j]表示当前在i个点时，处于循环的第j个位置。枚举前状态f【k，j-1】进行状态更新就行。
虽然算法不够优秀，但也足以AC。

在分析下楼下几位的程序：他们直接把j这层给省去了，直接枚举两个点。相当于每次j都是当前最大的
但我总觉的有问题。就是也许我第i个点并不是处于j最大的时候最好，也许我j助于循环的第1个，但是可以给后面
递减的服务；但如果当前最大的是处于t+2时，后面就必须是递增才能更新，可能会有bug。

不知道自己想的对不对。如果大家有什么看法，欢迎call我的QQ：841249284 峰哥

var Tmp,T,i,j,k,l,m,n,Ans:Longint;
A,F:array[0..2000] of Longint;
Begin
Readln(N,T);
For i:=1 to N do Begin Read(A[i]);F[i]:=1;End;
For i:=1 to N do
For j:=1 to i-1 do
If F[j]+1>F[i] then
Begin
Tmp:=(F[j]-1) mod (2*T);
If (Tmp<T)and(A[i]<A[j])or
(Tmp>=T)and(A[i]>A[j]) then F[i]:=F[j]+1;
End;
Ans:=0;
For i:=1 to N do
If F[i]>Ans then Ans:=F[i];
Writeln(Ans);
End.

测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 568 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 572 KiB, score = 20
测试数据 #3: Accepted, time = 15 ms, mem = 568 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 568 KiB, score = 40
Accepted, time = 15 ms, mem = 572 KiB, score = 110

读题最难了。改了七八遍发现题意理解错了。
对半周期的理解：t是被击中的目标的半周期。也就是说击中t个目标之后单调性发生变化。
对样例的解释：
导弹高度a.
打击到第I个导弹最多拦截的导弹数f.
a:1 3 2 4 5 6 9 7 8 10
f:1 1 2 3 3 3 3 4 5 5
解释：第一个：1。
第二个：放弃第一个，直接打第二个。
第三个：打完第二个，再打第三个。
第四个：打完第三个，再打第四个。
第五个：打完第三个，再打第五个。
第六个：打完第三个，再打第六个。
第七个：打完第三个，再打第七个。
第八个：由第七个下降得。
第九个：第八个上升。

第十个：第八个上升。

其实就是动态规划。题目描述太不清晰。

program aigo;
var
a:array[1..2000] of longint;
f:array[1..2000] of longint;
n,t:longint;
i,j:longint;
k,l:longint;
function gt(x:longint):longint;
begin
exit((x-1) div t);
end;
begin
readln(n,t);
for i:=1 to n do
begin
read(a[i]);
f[i]:=1;
end;
readln;
k:=0;
for i:=2 to n do
begin
l:=0;
for j:=1 to i-1 do
if f[j]>l then
if odd(gt(f[j])) then
begin
if a[i]>a[j] then l:=f[j];
end
else
begin
if a[i]<a[j] then l:=f[j];
end;
f[i]:=l+1;
if f[i]>k then k:=f[i];
end;
writeln(k);
end.
Markdown Test

var n,t,i,j,k,max:longint;
h,f:array[0..2001] of longint;
begin
readln(n,t);
for i:=1 to n do
read(h[i]);
for i:=1 to n do f[i]:=1;

for i:=2 to n do
for j:=1 to i-1 do
if f[i]<f[j]+1 then
begin
k:=(f[j]+t-1) div t;
if (odd(k)) and (h[i]<h[j]) then f[i]:=f[j]+1;
if (not odd(k)) and (h[i]>h[j]) then f[i]:=f[j]+1;
end;
for i:=1 to n do
if f[i]>max then max:=f[i];
writeln(max);
end.

我晕。。。。。

想了个朴素方程。。。

2000*2000*20

本以为超时，竟然秒杀。。。。。

囧。。。。。。。。。。。。。。。。。。。。。

编译通过...

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

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

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

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

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

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

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

借鉴了一个好思路：

设f表示第i个位置是在k时刻被打下来(1

首先比较容易想到用boolean型转移哈~

即f表示第i个作为第j个目标是否可行:

f={f or f[k,j-1] |

(0H[T] >H[T+1]

H[T+1]　　< H[T+2]　...　< H[2T] H[2T+2] ... > H[3T] >H[3T+1]

H[3T+1]　 < H[3T+2] ... < H[4T] h[i]

为奇数时,需满足当前 h[k]

Flag 　　 Accepted

题号 　　P1686

类型(?) 　　动态规划

通过 　　100人

提交 　　240次

通过率 　　42%

难度 　　3

哇哈哈。第100个AC。

f[j] 表示 长度为i的合法序列第i个最优是多少

if better(i,j)

then f[j+1]:=h[i];

function better(i,j:longint):boolean;

begin

if (((j-1) div t)and 1=0)and(h[i]>=f[j])and(j0)

then exit(false);

if (((j-1) div t)and 1=1)and(h[i]f[j+1])or(f[j+1]=-1))

then exit(true);

if (((j div t)and 1)=1)and((h[i]

第88个……

原先想状态里面还要包括现在是前半周期还是后半周期、现在是所在半周期的第几个，后来发现只要知道现在是第几个打下来的，就可以知道上面那两个了……脑子进水了…… 囧啊……

给这题加了1%的通过率

给我自己加了1%的通过率……

在周围几个货色的讨论声中萌生了做掉此题的念头,

开头硬是搞不清题目意思,不过zhh把图一画就很显得明了了..

这边是这样判断属于哪个周期的.

第i个数在其所属周期内的编号为m

记为f[i]=m

比如 半周期为3,有一如下周期

　1　　　　　7　　　　　　　13

　　2　　　6　8　　　　12 ..

　　　3　5　　　9　　11

　　　　4　　　　　10

..为了懒得写麻烦的判断就把所有编号都减了2,即初值都赋-1;

可得

　-1　　　　5　　　　　　11

　　0　　　4　6　　　　10 ..

　　　1　3　　　7　　9

　　　　2　　　　　8

这样我们可以发现 (m mod turn) 如为偶数则属于递减序列,如为奇数则为递增序列..

如此~

最后将搜索出来的编号最大值加上2即可

这题最难的是读懂题目，我被它的字母弄晕了~~~

自己手算了样例后才明白这题其实很简单……

就是求最长子序列时判断周期，再决定按递增序还是递减序DP

只要注意一点：上下周期的划分!!!

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

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

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

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

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

F[J]..F[J]-1..贡献3次WA..我的AC率..