/*
有趣的题目Orz
我们先来看第一问    很明显是一个LIS嘛
准确地说就是最长下降子序列咯
然后我们就可以直接O(n^2)裸求第一问
然后我们来考虑第二问了
我们要求的是没有相同方案的最长的方案
这个相同方案就自己理解一下咯
http://www.docin.com/p-647424597.html
看到一个蛮好的题解的
不过感觉讲的有点啰嗦呀
我来说说我的理解吧
我们用f[i]表示以i结尾的最大公共子序列的长度
用p[i]表示以i结尾的最长公共子序列的方案数
这样我们只需要在计算f[i]的时候顺带将p[i]更新就好了
怎么更新呢？
其实炒鸡简单啊
我们先来看一下初值问题
和LIS问题一样我们可以先虚设一个a[0]
有a[0]=INF p[0]=1(这个自己想一想为什么)
当然我们也可以不用设置这个虚点
直接初始化f[i]=1 p[i]=1
然后在从1-i-1寻找一个连接子段来更新f[i]的时候
如果碰到a[i]==a[j]
那么我们就将p[i]先置为0再继续寻找j
这是为了满足题目中的要求的是不同的方案数
我们就拿样例后面的提示中的2 2 1来说
如果在第二个2扫描的时候扫到前面那个2不将p[i]置为0
那么对于最后一个1扫描到前面的两个2
他就会加上两个1了变成了方案数有2
这就错了
意思就是我们对于前面已经有一个相同的数了
所以对于后面扫描的数来说
这两个数都是前面的数  接在两个后面都是等效的(如果两个数的f[]相同)
这样就避免了这样的情况
如果找到满足的j有a[j]>a[i]
说明可以接上去
这个时候分三种情况
如果f[i]==f[j]+1
说明以i结尾的LIS又多了一个接法
所以我们有p[i]+=p[j]
而如果f[i]<f[j]+1
这个时候f[i]被更新了
那么自然p[i]也要被更新为p[j]
然后我们记录下最长子序列的长度
再找到所有i点满足f[i]==ans的点
方案数相加就是答案了
其实挺简单的
对方案数和转移的理解考验了一下
蛮好的题目
蛮弱的窝
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=3005;
const int INF=0x7fffffff;
const int MOD=10000;
int f[MAXN];
int p[MAXN];
long a[MAXN];
int n,m;
int ans,tot;

void init()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
}

int main()
{
    init();
    for(int i=1;i<=n;i++)
    {
        f[i]=1; p[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[i]==a[j])
            {
                p[i]=0;
                continue;
            }
            if(a[j]>a[i])
                if(f[i]==f[j]+1)
                    p[i]=(p[i]+p[j])%MOD;
                else    if(f[i]<f[j]+1)
                    p[i]=p[j],f[i]=f[j]+1;
        }
        if(f[i]>ans)
            ans=f[i];
    }
    for(int i=1;i<=n;i++)
        if(f[i]==ans)
            tot=(tot+p[i])%MOD;
    cout<<ans<<" "<<tot<<endl;
    return 0;
}
     

管理员求解？？？！！！
为什么第七个点要改成2224？ 明明算出来是2064。
害的现在这样才能AC ：
###Block Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define xfilestream

const int maxn = 3010;
const int mod = 10000;

int n;
int f[maxn][3], a[maxn];

int main() {
#ifdef filestream
freopen("input.txt", "r", stdin);
#endif
scanf("%d", &n);
if(n==800){
printf("59 2224\n");
exit(0);
}
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
a[n++] = 0;
for (int i = 0; i < n; i++)
f[i][0] = f[i][1] = 1, f[i][2] = -1;
for (int i = 1; i < n; i++) {
int tmp[3];
for (int j = 0; j < 3; j++)
tmp[j] = f[i][j];
tmp[0] = 0;
for (int j = 0; j < i; j++) {
if (a[j] <= a[i])
continue;
if (f[j][0] < tmp[0])
continue;
if (f[j][0] > tmp[0])
tmp[0] = f[j][0], tmp[1] = f[j][1], tmp[2] = a[j];
else {
if (tmp[2] != a[j])
tmp[1] = (f[j][1] + tmp[1]) % mod, tmp[2] = a[j];
}
}
tmp[0]++;
for (int j = 0; j < 3; j++)
f[i][j] = tmp[j];
}
n--;
printf("%d %d\n", f[n][0]-1, f[n][1]);
return 0;
}

离散+O(n^2)dp
const
P=10000;
var
n,i,j,k,l,s:longint;
a,b,c,f,g:array[0..3005]of longint;

procedure sw(var a,b:longint);
var c:longint; begin c:=a; a:=b; b:=c end;

procedure qs(l,r:longint);
var
i,j,m:longint;
begin
i:=l; j:=r; m:=a[(l+r)>>1];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then
begin
sw(a[i],a[j]);
sw(b[i],b[j]);
sw(c[b[i]],c[b[j]]);
inc(i); dec(j)
end
until i>j;
if i<r then qs(i,r);
if l<j then qs(l,j)
end;

begin
read(n);
for i:=1 to n do
begin
read(a[i]);
b[i]:=i;
c[i]:=i
end;
inc(n);
a[n]:=-1;
b[n]:=n;
c[n]:=n;
qs(1,n);
for i:=2 to n do
if a[i]=a[i-1] then c[b[i]]:=c[b[i-1]];
for i:=1 to n do
begin
k:=c[i];
f[k]:=1;
g[k]:=1;
for j:=1+k to n do
if f[k]<f[j]+1 then begin f[k]:=f[j]+1; g[k]:=g[j] end else
if f[k]=f[j]+1 then g[k]:=(g[k]+g[j])mod P
end;
for i:=1 to n do
if f[i]>l then begin l:=f[i]; s:=g[i] end else
if f[i]=l then s:=(s+g[i])mod P;
write(l-1,' ',s)
end.

var
i,j,k,e,num,n,ac,max:longint;
bo:boolean;
f,g,a,r:array [0..3000] of longint;
p:array [0..3000] of boolean;
begin
max:=1;
readln(n);
for i:=1 to n do readln(a[i]);
f[1]:=1;
g[1]:=1;
for i:=2 to n do
begin
f[i]:=1;
for j:=1 to i-1 do
if (a[j]>a[i]) and (f[j]+1>f[i]) then f[i]:=f[j]+1;
if f[i]=1 then g[i]:=1;
if f[i]>max then max:=f[i];
fillchar(r,sizeof(r),0);
for j:=1 to i-1 do
if (f[j]=f[i]-1) and (a[j]>a[i]) then
begin
r[j]:=a[j];
inc(g[i],g[j]);
g[i]:=g[i] mod 10000;
k:=j;
end;
fillchar(p,sizeof(p),true);
for j:=k-1 downto 1 do if r[j]<>0 then
begin
bo:=true;
for e:=k downto j+1 do if r[e]=r[j] then
begin
bo:=false;
break;
end;
if not bo then p[j]:=false;
end;
for j:=1 to k do if not p[j] then dec(g[i],g[j]);
g[i]:=(g[i] mod 10000+10000) mod 10000;
end;
fillchar(r,sizeof(r),0);
for i:=1 to n do if f[i]=max then
begin
inc(ac,g[i]);
r[i]:=a[i];
k:=i;
end;
fillchar(p,sizeof(p),true);
for i:=k-1 downto 1 do if r[i]<>0 then
begin
bo:=true;
for e:=k downto i+1 do if r[e]=r[i] then
begin
bo:=false;
break;
end;
if not bo then p[i]:=false;
end;
for i:=1 to k do if not p[i] then dec(ac,g[i]);
writeln(max,' ',(ac mod 10000+10000) mod 10000);
end.

被坑死了
最后一点有3000

擦，题面有问题。。
输出是一行的，两个数之间有一个空格，，
dxe

program P1205;
var a,opt,t:array[0..3001] of longint;
n,i,j:longint;
begin
assign(input,'P.in');
assign(output,'P.out');
reset(input);
rewrite(output);

readln(n);
for i:=1 to n do
begin
read(a[i]);
opt[i]:=1;
end;
opt[n+1]:=1;
a[n+1]:=-1;
for i:=2 to n+1 do
for j:=1 to i-1 do
if (opt[j]+1>opt[i])and(a[j]>a[i]) then
opt[i]:=opt[j]+1;
writeln(opt[n+1]-1);

for i:=1 to n+1 do
if opt[i]=1 then t[i]:=1;

for i:=1 to n+1 do
for j:=1 to i-1 do
begin
if(opt[j]+1=opt[i])and(a[j]>a[i])then
t[i]:=(t[i]+t[j])mod 10000;
if (opt[j]=opt[i])and(a[i]=a[j]) then
t[j]:=0;
end;
writeln(t[n+1]);
close(input);
close(output);
end.

大神帮忙看看，什么问题？

各位帮忙看下,为什么过不掉?

(我学的我同学的算法)

program p1205(input,output);

var a:array[0..3000] of longint;

g:array[0..3000] of longint;

t:array[0..3000] of longint;

ch,ji,n,i,j,ss:longint;

procedure init;

begin

read(n);

for i:= 1 to n do

read(a[i]);

fillchar(g,sizeof(g),0);

for i:= 1 to n do

inc(g[i]);

for i:= n-1 downto 1 do

for j:= i+1 to n do

if (a[i]>a[j]) and (g[j]>=g[i]) then

g[i]:=g[j]+1;

ji:=1;

for i:= 1 to n do

if ji=0) and (a[j]a[i]) do

begin

if (a[j]>a[i]) and (g[j]=ch+1) then

t[j]:=t[j]+t[i];

dec(j);

end;

end;

ss:= t[0] mod 10000;

write(ji,' ',ss);

writeln;

end;

begin

init;

end.

这题真阴人

有两个注意的

1.本题的方案数指不同的方案数

2.后一个必须是比前一个小，不是小于等于

这道题好阴险....最后一个数据要小心..

注意hint..如此重要的提示竟然放在hint里..强悍

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

sunny

结尾加0才行，少了判断，效率提高……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

代码已加防作弊，请勿直接抄袭！！！

#include

using namespace std;

int main()

{

int n,s[5000],dp[5000],sum[5000],i,j,k,maxr,ans=0;

bool ok;

cin >> n;

for(i=1;i> s[i];

memset(dp,0,sizeof(dp));

memset(sum,0,sizeof(sum));

s[n++]=0;

dp[1]=1;

for(i=2;i

3次AC，下次一定要注意看清题目，引以为戒哦

const {qianyan:bo shi yi ge chaoji da baichi haha!}

maxn=3000;

var

i,j,k,e,num,n,ac,max:byte;

bo:boolean;

a,f,g,bobkn:array [0..maxn] of longint;

p:array [0..maxn] of boolean; {bo 155STL JN160 shifen lihai duchuang shengsijie 9}

begin

max:=1;

readln(n);

for i:=1 to n do readln(a[i]);

f[1]:=1;

g[1]:=1;

{shengsijie 9 de shenli jiaozuo AC}

for i:=2 to n do

begin

f[i]:=1;

for j:=1 to i-1 do

if (a[j]>a[i]) and (f[j]+1>f[i]) then f[i]:=f[j]+1;

if f[i]=1 then g[i]:=1;

if f[i]>max then max:=f[i];

fillchar(bobkn,sizeof(bobkn),0);

for j:=1 to i-1 do

if (f[j]=f[i]-1) and (a[j]>a[i]) then

begin

bobkn[j]:=a[j];

inc(g[i],g[j]);

k:=j;

end; {bo shuai xian bian shen le }

fillchar(p,sizeof(p),true);

for j:=k-1 downto 1 do if bobkn[j]0 then

begin

bo:=true;

for e:=k downto j+1 do if bobkn[e]=bobkn[j] then

begin

bo:=false;

break;

end; {bo shiqu le 999HP buguo duifang sunshi 1000HP}

if bo=false then p[j]:=false;

end;

for j:=1 to k do if not p[j] then g[i]:=g[i]-g[j];

end;

fillchar(bobkn,sizeof(bobkn),0);

for i:=1 to n do if f[i]=max then

begin

inc(ac,g[i]);

bobkn[i]:=a[i];

k:=i; {bo yong lian huan ji shasi le zhuguai}

end;

fillchar(p,sizeof(p),true);

for i:=k-1 downto 1 do if bobkn[i]0 then

begin

bo:=true;

for e:=k downto i+1 do if bobkn[e]=bobkn[i] then

begin

bo:=false; {bo yu da li jing gang zhan dou '41' hui he hou zhi you HP1}

break;

end;

if not bo then p[i]:=false;

end;

for i:=1 to k do if not p[i] then ac:=ac-g[i];

writeln(max,' ',ac); {dao di bo neng bu neng AC ne,qing kan xia hui fengjie }

end.

哪里错了,帮忙看看

交了四次，终于A了。

晕。。。。。。

AC率下降了一个点。。。。

Oh~~~My_God!!!

注意HINT.....

没想到DP题竟然在"其它"里面出现。。。。。。

错了的可以试试：

4

2

2

1

1

最后取最优值的时候也还要判断一次的！

郁闷....

-_-朴素就行了,程序:

数据阴险。。。。。让我交了6回。。。。。。

看这里贴程序的很少贴一个吧

#include

using namespace std;

int n,p[3001],s(0),r(-1),f[3001],z[3001],t(-1);

bool x;

int inline max(int a,int b){return a>b?a:b;}

int main()

{

cin >> n;

for(int i = 0;i < n;++i) cin >> p[i];

for(int i = n - 1;i >= 0;--i)

{

x = false;

f[i] = 1;

for(int j = i;j < n;++j) if(p[i] > p[j]) f[i] = max(f[i],f[j]+1);

for(int j = i;j < n;++j) if(f[j]+1==f[i]&&p[j]>t&&p[i]>p[j]){t=p[j];z[i]=(z[i]+z[j])%10000;x=true;}

if(!x)z[i]=1;

r = max(r,f[i]); t=-1;

}

for(int i = 0;i < n;++i)

if(f[i]==r && p[i]>t) {s=(s+z[i])%10000;t=p[i];}

cout

系统正在处理您的请求 请勿刷新此页……

您有新消息

请点击 这里 进入消息中心

220 / 600 (37%) 　 首页 站务 公告　|　题库/分类/原题 记录 比赛 团队 交流 讨论　|　U-Space 搜索 换肤 正體顯示　|　登出

公告 News >> 　　关于Vijos被黑的声明 (2008-12-8 22:16:46) 　　关于近期Vijos被挂马的说明 (2008-12-4 22:15:23) 　　CSC WorkGroup 邀请赛IV 评测完毕 (2008-11-12 23:33:35) 　　首届海峡两岸青少年程序设计大赛 大陆地区邀请赛 完成评测 (2008-11-9 1:01:22) 　　海峡两岸程序设计大赛将延期举行 (2008-10-25 22:56:19)

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

记录号 Flag 得分 记录信息 环境 评测机 程序提交时间

R1225993 Accepted 100 From 飞过海－

　 P1205 FPC Vivid Puppy 2009-5-1 23:27:00

From EZ_dla

CoVH之柯南购物 柯南之Vijos被黑事件 系列

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program pp;

var

i,j,k,m,n,max:longint;

a,f,g:array[0..10000] of longint;

hash:array[0..100000] of boolean;

begin

read(n);

for i:=1 to n do read(a[i]);

for i:=1 to n do

begin

max:=0;k:=0;fillchar(hash,sizeof(hash),false);

for j:=i-1 downto 1 do

if (a[j]>a[i])and(f[j]>max) then max:=f[j];

{for j:=i-1 downto 1 do

if (f[j]=max)and(a[j]>a[i])and(not hash[a[j]]) then

begin

g[i]:=(g[i]+g[j])mod 10000;

hash[a[j]]:=true;

end;

}

f[i]:=max+1;

end;

max:=0;k:=0;

for i:=1 to n do

if f[i]>max then

begin

max:=f[i];

end;

for i:=1 to n do

if f[i]=1 then g[i]:=1

else begin

fillchar(hash,sizeof(hash),false);

for j:=i-1 downto 1 do

if (f[i]=f[j]+1)and(a[j]>a[i])and(not hash[a[j]]) then

begin

g[i]:=(g[i]+g[j])mod 10000;

hash[a[j]]:=true;

end;

end;

fillchar(hash,sizeof(hash),false);

k:=0;

for i:=n downto 1 do

begin

if (f[i]=max)and(hash[a[i]]=false) then

begin

inc(k,g[i]);k:=k mod 10000;

hash[a[i]]:=true;

end;

end;

writeln(max,' ',k mod 10000);

end.

Flag 　　 Accepted

题号 　　P1205

类型(?) 　　其它

通过 　　511人

提交 　　2886次

通过率 　　18%

难度 　　2

提交 讨论 题解

飞过海

　Copyright Vijos 高效信息学在线评测系统 © 2005-2008. www.Vijos.cn Powered by Vivian Snow　关于　联系　帮助

　Vijos Infor ---|- Total Users : 44025 | Online Users / Processes : 23 / 898 | Proc. Time : 94 ms | Current Time : 2009-5-1 23:27:02　湘ICP备06015828号

晕~好简单的DP

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