QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #37956 | #1191. Reordering the Documents | zshccc | RE | 4ms | 11836kb | C++ | 1.8kb | 2022-07-03 15:35:04 | 2022-07-03 15:35:05 |
Judging History
answer
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define SZ(a) ((int)(a.size()))
#define rep(i,a,b) for(int i=a;i<b;i++)
#define mp make_pair
using namespace std;
// dp[i][j][k]//i为当前位置，j为第二大值，k为第二大的长度
// 当j>sufmin(i+1~n)时，为无效状态，可以利用该性质优化
// 所以有j<sufmin...，每次转移的时候，只有该值为sufmin的时候才可以转移到sec
//
// dp[i][j][k]
const int N=510;
const int inf=1e9;
int dp[N][N][N];
int a[N];
int premax[N],sufmin[N];
signed main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
rep(i,1,n+1){
premax[i]=max(premax[i-1],a[i]);
}
sufmin[n+1]=inf;
for(int i=n;i>=1;i--){
sufmin[i]=min(sufmin[i+1],a[i]);
}
// dp[i][j][k]
// dp[i+1][j][k]=
// if(a[i+1]==premax[i+1]) dp[i][j][k]- >dp[i+1][premax[i]][i+1-k]; / dp[i+1][j][k];
// if(a[i+1]>j) dp[i][j][k]->dp[i+1][a[i+1]][k+1];
dp[0][0][0]=1;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=m;k++){
if(i<k)continue;
if(premax[i+1]==a[i+1]){
dp[i+1][premax[i]][i-k]+=dp[i][j][k]; //将a[i+1]放在j后面
dp[i+1][j][k]+=dp[i][j][k];
//将a[i+1]放在 最大序列后面
}
else if(a[i+1]>j){
dp[i+1][a[i+1]][k+1]+=dp[i][j][k];
}
}
}
}
int res=0;
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++)
if(n-i<=m)res+=dp[n][j][i];
}
cout<<res<<"\n";
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 11836kb
input:
6 3 1 3 4 2 6 5
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 2ms
memory: 11776kb
input:
6 6 1 3 4 2 6 5
output:
8
result:
ok answer is '8'
Test #3:
score: 0
Accepted
time: 3ms
memory: 7596kb
input:
4 4 4 3 1 2
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 4ms
memory: 11616kb
input:
6 3 1 3 4 2 6 5
output:
4
result:
ok answer is '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 9744kb
input:
6 6 1 3 4 2 6 5
output:
8
result:
ok answer is '8'
Test #6:
score: 0
Accepted
time: 3ms
memory: 7588kb
input:
4 4 4 3 1 2
output:
0
result:
ok answer is '0'
Test #7:
score: -100
Runtime Error
input:
1000 500 4 5 6 8 10 11 12 13 14 15 20 23 25 26 28 29 33 35 1 2 36 38 3 7 41 9 16 44 48 17 18 51 52 53 19 21 54 22 24 59 61 62 27 67 30 31 32 34 68 69 37 39 73 40 76 77 42 81 83 43 85 45 87 46 89 94 47 95 49 50 97 101 55 103 105 56 57 58 106 60 108 110 63 111 114 64 115 65 119 66 70 71 120 121 72 124...