4621: Tc605
Time Limit: 15 Sec Memory Limit: 128 MB
Submit: 328 Solved: 183
[Submit][Status][Discuss]
Description
最初你有一個長度為 N 的數字序列 A。為了友善起見，序列 A 是一個排列。 你可以操作最多 K 次。每一次操作你可以先標明一個 A 的一個子串，然後将這個子串的數字全部變成原來這個子串的最大值。問最終有幾種可能的數字序列。答案對 1e9+7 取模。
Input
第一行兩個數 N 和 K。第二行 N 個數，描述一個排列 A。 N,K<=500， 有6組資料N>100，有梯度
Output
輸出一個數，表示答案在模域下的值。
Sample Input
3 2
3 1 2
Sample Output
4
HINT
Source
TC 605 Hard
這道題的思想王聿中大神十分牛逼。
https://www.cnblogs.com/wangyurzee7/p/5554380.html
發現對于一個數可以操作的範圍是确定的，然後
發現最終的序列中，除了沒有操作的序列，如果操作了一定是1-k之間的段數。
f[i][j]表示分成了i段數，是1-j這些數産生的方案數，為什麼i為段數，
因為在更新的時候，比如x這個點，可以操作的範圍是l--r，那麼從f[i-1][l-r]中更新。
用到了字首和優化降低一維，變成了n^3
1 #pragma GCC optimize(2)
2 #pragma G++ optimize(2)
3 #include<iostream>
4 #include<algorithm>
5 #include<cmath>
6 #include<cstdio>
7 #include<cstring>
8
9 #define N 507
10 #define mod 1000000007
11 #define ll long long
12 using namespace std;
13 inline int read()
14 {
15 int x=0,f=1;char ch=getchar();
16 while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
17 while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
18 return x*f;
19 }
20
21 int n,K;
22 int a[N];
23 int f[N][N],delta[N];
24
25 int main()
26 {
27 f[0][0]=1;
28 n=read(),K=read();
29 for (int i=1;i<=n;i++)
30 a[i]=read();
31 for (int i=1;i<=n;i++)
32 {
33 int l,r;
34 for (l=i;l>1&&a[l-1]<a[i];l--);
35 for (r=i;r<n&&a[r+1]<a[i];r++);
36 (f[K][i]+=f[K][i-1])%=mod;
37 for (int k=K-1;k>=0;k--)
38 {
39 delta[l-1]=0;
40 for (int j=l;j<=r;j++)delta[j]=(delta[j-1]+f[k][j-1])%mod;
41 for (int j=l;j<=r;j++)(f[k+1][j]+=delta[j])%=mod;
42 (f[k][i]+=f[k][i-1])%=mod;//什麼都不操作
43 (f[k+1][i]+=mod-f[k][i-1])%=mod;//自己這個已經加過了
44 }
45 }
46 int ans=0;
47 for (int i=0;i<=K;i++)
48 (ans+=f[i][n])%=mod;
49 printf("%d\n",ans);
50 } 轉載于:https://www.cnblogs.com/fengzhiyuan/p/8487395.html