# 78 条题解

• @ 2021-11-13 21:51:01
``````#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long

ull f[104][104],sum;
int a[104];
{
register int x=0,f=0;register char ch=getchar();
while(ch<'0' || ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
signed main()
{
for(int i=2;i<=n;i++)
for(int j=i-1;j>=1;j--)
for(int k=2;k<=i;k++)
if(a[i]>=a[j])
f[i][k]=f[i][k]+f[j][k-1];
for(int i=1;i<=n;i++)sum+=f[i][m];
cout<<sum;

return 0;
}
``````
• @ 2018-07-27 19:49:07

开longlong！！！！！！！！！！太重要了

• @ 2019-08-05 13:01:15

预感到数据很大，就立马开了unsigned long long，一次水过。

``````#include <iostream>
#define ULL unsigned long long

using namespace std;

int n,m;
ULL dp[101][21]={0};//dp[i][j] 以i结尾的长度为j的非递减字串种数
int a[101]={0};

int main()
{
cin>>n>>m;
int i,j,k;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(j==1)
{
dp[i][j]=1;
}
for(k=1;k<i;k++)
{
if(a[k]<=a[i])
{
dp[i][j]+=dp[k][j-1];
}
}
}
}
ULL ans=0;
for(i=1;i<=n;i++)
{
ans+=dp[i][m];
}
cout<<ans<<endl;
return 0;
}
``````
• @ 2016-08-01 15:08:22

Vijos解题排名**前1000**纪念！！

编译成功...

Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
24 lines compiled, 0.0 sec, 28176 bytes code, 1268 bytes data

测试数据 #0: Accepted, time = 0 ms, mem = 8664 KiB, score = 5
测试数据 #1: Accepted, time = 15 ms, mem = 8664 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 8664 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 8664 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 8664 KiB, score = 5
测试数据 #5: Accepted, time = 15 ms, mem = 8664 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 8668 KiB, score = 5
测试数据 #7: Accepted, time = 0 ms, mem = 8664 KiB, score = 5
测试数据 #8: Accepted, time = 15 ms, mem = 8668 KiB, score = 5
测试数据 #9: Accepted, time = 0 ms, mem = 8664 KiB, score = 5
测试数据 #10: Accepted, time = 0 ms, mem = 8664 KiB, score = 5
测试数据 #11: Accepted, time = 0 ms, mem = 8664 KiB, score = 5
测试数据 #12: Accepted, time = 15 ms, mem = 8664 KiB, score = 5
测试数据 #13: Accepted, time = 15 ms, mem = 8668 KiB, score = 5
测试数据 #14: Accepted, time = 0 ms, mem = 8668 KiB, score = 5
测试数据 #15: Accepted, time = 15 ms, mem = 8664 KiB, score = 5
测试数据 #16: Accepted, time = 0 ms, mem = 8668 KiB, score = 5
测试数据 #17: Accepted, time = 0 ms, mem = 8668 KiB, score = 5
测试数据 #18: Accepted, time = 15 ms, mem = 8664 KiB, score = 5
测试数据 #19: Accepted, time = 15 ms, mem = 8668 KiB, score = 5
Accepted, time = 120 ms, mem = 8668 KiB, score = 100

• @ 2016-07-13 19:29:33

数据太弱了吧、、、三重循环都能A。。
设f[i][j]表示以A[i]结尾长度为j的不下降子序列个数
f[i][j]=sum(f[k][j-1]) (A[k]<=A[i])
~~~
#include <cstdio>
#include <cstdlib>
long long int n,m,ans,A[105],f[105][100];
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",A+i);
}
for(int i=1;i<=n;i++)
f[i][1]=1;
for(int i=1;i<=n;i++){
for(int j=2;j<=m;j++){
if(j>i)break;
for(int k=1;k<i;k++)
if(A[k]<=A[i]) f[i][j]+=f[k][j-1];
}
}
for(int i=1;i<=n;i++){
ans+=f[i][m];
}
printf("%lld\n",ans);
return 0;
}

• @ 2013-10-24 19:33:11

！！！！！！！！！！！！！！！！注意开long long！！！！！！！！！！！！！
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 692 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 696 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 696 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 696 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 692 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 688 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 700 KiB, score = 5
测试数据 #7: Accepted, time = 0 ms, mem = 692 KiB, score = 5
测试数据 #8: Accepted, time = 0 ms, mem = 692 KiB, score = 5
测试数据 #9: Accepted, time = 0 ms, mem = 688 KiB, score = 5
测试数据 #10: Accepted, time = 0 ms, mem = 696 KiB, score = 5
测试数据 #11: Accepted, time = 0 ms, mem = 692 KiB, score = 5
测试数据 #12: Accepted, time = 0 ms, mem = 696 KiB, score = 5
测试数据 #13: Accepted, time = 0 ms, mem = 692 KiB, score = 5
测试数据 #14: Accepted, time = 0 ms, mem = 696 KiB, score = 5
测试数据 #15: Accepted, time = 0 ms, mem = 696 KiB, score = 5
测试数据 #16: Accepted, time = 0 ms, mem = 696 KiB, score = 5
测试数据 #17: Accepted, time = 0 ms, mem = 696 KiB, score = 5
测试数据 #18: Accepted, time = 0 ms, mem = 696 KiB, score = 5
测试数据 #19: Accepted, time = 15 ms, mem = 696 KiB, score = 5
Accepted, time = 15 ms, mem = 700 KiB, score = 100
代码
#include<cstdio>
#include<cstring>
int n,m,num[103],N=0;
long long ans=0,res[2][101][101];
int main(){
scanf ("%d%d",&n,&m);
memset(res[0],0,sizeof res[0]);
for (int i=1 ; i<=n ; i++) scanf("%d",&num[i]);
for (int z=1 ; z<=n ; z++) res[0][z][z]=1;
for (int z=2 ; z<=m ; z++){
N=1-N;
memset(res[N],0,sizeof res[N]);
for (int i=1 ; i<=n-z+1; i++)
for (int j=i+z-1; j<=n ; j++)
for (int k=i+1 ; k<=j-z+2; k++)
if ( num[ k ] >= num[ i ] ) res[N][i][j]+=res[1-N][k][j];

}
for (int i=1 ; i<=n-m+1; i++)
for (int j=i+m-1; j<=n ; j++) ans+=res[ N ][i][j];
printf("%I64d",ans);
}

• @ 2012-08-12 17:09:11

手贱加了个高精

• @ 2009-11-11 17:57:56

我爱边读边处理^_^

• @ 2009-11-10 10:00:51

本来以为这种水题一次就ac，结果没开int64……

第三组数据啊，害死我了

• @ 2009-11-08 20:39:23

总算AC了，第三组数据害死人~~~

一定要把f[i][i]和ans统统改成long long

我就因为这个挂了一次……

• @ 2009-11-07 19:14:45

闹了半天 不管重复的呀....

要是加上判重该怎么做呢？ 有谁想出来吗？ 交流一下？

• @ 2009-10-31 22:01:33

搜索怎么也过不了第三个点……

还是dp好，少了两行代码，还秒杀

• @ 2009-10-29 16:11:51

不仅是数组

ans也要用int64

• @ 2009-10-26 20:42:40

伤了，伤了..

数组改成long long，累加f[i][m]的变量忘改了..

• @ 2009-10-23 21:59:13

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

哎...看了题解才知道用int64...我的AC率啊

f:=f+f[k,j-1];

初值f:=1;

最后把f累加.注意int64!

• @ 2009-10-22 20:20:43

错误号106是什么呢……

int64！

本菜做法：记录以第i个数为最后一个数，长度为j的不下降子序列个数，然后递推

• @ 2009-10-18 22:39:13

我也没看..

f数组和ans全部用int64就过了..

• @ 2009-10-18 15:03:29

第三个点longint会挂的 要开qword

题目那么长，全是废话 我看都没看 直接看输入格式就直接做了

• @ 2009-10-18 11:17:02

第三组数据到底是什么啊？为什么就是过不去？

• @ 2009-09-16 18:03:03

为什么EXTENDED过不了第三组............INT64又可以..........why

ID
1408

4

(无)

1115

442

40%

2