78 条题解
-
1
ugly LV 8 @ 2024-11-15 20:34:45
不知道现在还在用vijos的人还有多少，看到的都是很久以前的评论了。。。
回归正题，看到了楼下的两位仁兄的题解，感觉可以做点补充。
这个题的第一问不用多说，经典的LIS，大伙应该都会做，主要是第二问，理解了题目要求的方案数目后，必须考虑到怎么去除重复的方案数这个问题。
不妨也假设用f[i]表示以i结尾的最大公共子序列的长度，用p[i]表示以i结尾的最长公共子序列的方案数,那么p[i]就应该等于所有可以转移到当前f[i]（假设f[i]已经求出）的那些前面的数的各自方案数去重之后的和，去重很显然的一点是，能转移到当前状态的数如果不同，那必然是不同的方案嘛，只有前一个数是相同的数才要考虑去重。
首先说明一点，对于前面那些能转移到当前位置的数，它们形成的一定是一个非降的序列，不然就跟我们dp的状态表示是矛盾的了（这点应该很好理解吧），所以相同的数一定是出现在一起的，不会分散地出现在这个序列中。
关键就是这里了，我们必须考虑到一种情况（题面的例子我觉得举得不够好），比如下面这样的数列：
8 6 5 7 5 4
假如我们要计算4这个位置的p[i],显然4前面的2个5都是可以转移到4的，我们可以发现，第一个5的p[i]是1，就是8 6 5嘛，但是第二个5的p[i]是2！除了和前面一样的8 6 5外，还有 8 7 5这种可行的方案，那我们怎么去重呢？其实想想就能发现，如果两个一样的数都能进行转移，那么右边这个数对应的p[i]一定是大于等于左边这个数的p[i]的，因为左边这个数能形成的方案，右边这个数一定也可以形成，而且右边这个数还可能包含一些独特的方案，这部分就是右边的数的p[i]比左边数的p[i]多出来的值了。那等等，我们不是只要取最右边这个数的p[i]就行了嘛！它就包括了从这个数转移所有能形成的方案数！怎么实现呢，就用一个逆序的循环，上面说过，相同的数一定连续出现，第一个碰到的就是最右边的，其他相同的直接跳过就好了！（好吧，其实这个确实很简单，不过本人一开始没注意到这点，以为相同的数的p[i]应该都是一样的，所以犯了和楼下那位说第七个点不对的老哥一样的错误，循环顺序写的是i从小到大遍历的，所以取的是最左边的数的p[i],一直卡在第七个点过不去。。。）
懂了这个就好写了，不过我还想对楼下这位PowderHan老哥的代码说点题外话。。。他的这个代码中，p[i]其实并不是表示以i结尾的最长公共子序列的方案数，对于可能进行转移的相同的数，他的p[i]的存储逻辑是类似差分数组一样的，第一个数的p[i]确实是表示以i结尾的最长公共子序列的方案数，但是后续的p[i]存储的是这个数和上一个数之间新的方案数（就是我上面例子里面的说的那种情况，多出来的方案数），也就是真正意义上的当前位置p[i]和前面那个相同的数的p[i]的差值，所以在最后求和的时候各个位置的p[i]直接相加就行了，刚好复原为正确的值。
最后有一个小技巧，也是老生常谈了，提一嘴。可以在最后自己增加一个新的商品，价值为0（或者更保险一点取负数，谁知道有没有老板白送商品呢，笑），加了这个虚点后，对这n+1个商品dp，可以保证最大公共子序列一定是以这个虚点结尾的，这个序列的长度-1就是第一问的答案了（记得去掉这个虚点占的一个长度），而第二问的方案数也就是这个点的方案数了，不需要最后再去找能转移到这个点的各个数字的方案数并去重求和了。
我自己的代码：#include <iostream> using namespace std; int main() { int n; cin >> n; int price[n + 1], count[n + 1], scheme[n + 1]; // count是子序列长度dp数组，scheme是方案数dp数组 for (int i = 0; i < n; ++i) cin >> price[i]; price[n] = -1; // 加虚点 for (int i = 0; i < n + 1; ++i) { count[i] = 1; for (int j = 0; j < i; ++j) // 先求count[i] if (price[j] > price[i]) count[i] = max(count[i], count[j] + 1); if (count[i] == 1) // 如果以当前位置结尾的子序列长度为1，说明只有当前位置这个数，方案数当然是1 { scheme[i] = 1; continue; } scheme[i] = 0; // 否则置为0，准备累加转移来的去重方案数 int last = -1; for (int j = i - 1; j >= 0; --j) // 一定是由大到小 { if (price[j] > price[i] && count[j] == count[i] - 1) // 找出所有能转移的位置 { if (last != -1 && price[last] == price[j]) // 如果是相同的数字就直接跳过，这些相同的数字只取最右边的方案数加上去 continue; last = j; scheme[i] += scheme[j]; scheme[i] %= 10000; } } } cout << count[n] - 1 << " " << scheme[n] << endl; return 0; } -
1
/* 有趣的题目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; } -
0
1464942666 LV 8 @ 2015-12-30 14:16:32
管理员求解？？？！！！
为什么第七个点要改成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;
} -
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. -
0
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. -
0
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.
大神帮忙看看，什么问题？ -
0
各位帮忙看下,为什么过不掉?
(我学的我同学的算法)
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. -
0
yulingtai01 LV 9 @ 2009-10-22 20:41:09
这道题好阴险....最后一个数据要小心..
注意hint..如此重要的提示竟然放在hint里..强悍 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 56ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：56mssunny
-
0
结尾加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 -
0
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.
哪里错了,帮忙看看 -
0
lemon_TsyD LV 9 @ 2009-07-20 00:06:18
数据阴险。。。。。让我交了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 -
0
系统正在处理您的请求 请勿刷新此页……
您有新消息
请点击 这里 进入消息中心
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:00From 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 有效耗时：0msprogram pp;
var
i,j,k,m,n,max:longint;
a,f,g:array[0..10000] of longint;
hash:array[0..100000] of boolean;
beginread(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号
ugly
LV 8
@ 2024-11-15 20:34:45
