@TryMyEdge
2016-12-09T13:15:20.000000Z
字数 14157
阅读 1301
题解
A Design Tutorial: Learn from Math
题目大意：
给定一个n（12<=n<=10^6)，求出符合以下要求的x和y：
1.x+y=n。
2.x和y都是合数。
解题思路：
显然，若n为偶数，可以表示为两个偶数相加；若n为奇数，可以表示为一个奇数加一个偶数。而大于2的所有偶数都是合数，最小的偶合数为4，最小的奇合数为9。所以大于等于12的偶数可以表示为4+（n-4），大于12的奇数可以表示为9+（n-9）。
时间复杂度O（1），空间复杂度O（1）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;int main(){int x;cin>>x;if(x%2)cout<<9<<" "<<x-9<<endl;elsecout<<4<<" "<<x-4<<endl;return 0;}
B Design Tutorial: Learn from Life
题目大意：
有n（1≤n≤2000）个人坐电梯，已知电梯一次载客的上限k（1≤k≤2000）和这n个人分别要去的层数f（2≤f[i]≤2000），所有人初始都在1层，求电梯将所有人送往他们要去的层数后回到1层所花的最少时间。
解题思路：
因为电梯上下人不花时间，花费时间的只有电梯的升降，所以显然一趟运送的时间只和所运的最高楼层的那个人有关，其他人都可以在运的路程中抵达。同时多运人对时间不会有影响。所以每次运尽量多的人，并且运的是剩下的人中楼层最高的那部分。所以只要将这n个数排序，每次运最大的那部分，直到运完。
时间复杂度O（n*logn），空间复杂度O（n）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;int n,k,t=0;int num[2005];bool cmp(int x,int y){return x<y;}int main(){cin>>n>>k;for(int i=0;i<n;i++)scanf("%d",num+i);sort(num,num+n);while(n){t+=2*(num[n-1]-1);n=max(n-k,0);}cout<<t<<endl;return 0;}
C Design Tutorial: Make It Nondeterministic
题目大意：
有n（1≤n≤10^5）个人，给出每个人的两个备选名字（每个名字只包含不超过50字符且全为小写字母，保证这2*n个名字各不相同），每个人分别选择使用其中一个名字，给出一个这n个人排列顺序，问是否有一种情况，给出的排列人的名字满足字典序。
解题思路：
把这n个人按照给定的顺序排序，dp[i][j]表示到第i个人为止，第i个人用第j个名字是否可行，0表示不可行，1表示可行。name[x][y]表示序号为x的人的第y个名字，num[i]表示给定排列中第i个人的序号。
状态转移：
0.dp[0][0]=dp[0][1]=1;
1.dp[i][0]=dp[i][1]=0，初始化;
2.如果name[num[i]][0]>name[num[i-1]][0]并且dp[i-1][0]为1，dp[i][0]为1；
3.如果name[num[i]][0]>name[num[i-1]][1]并且dp[i-1][1]为1，dp[i][0]为1；
4.如果name[num[i]][1]>name[num[i-1]][0]并且dp[i-1][0]为1，dp[i][1]为1；
5.如果name[num[i]][1]>name[num[i-1]][1]并且dp[i-1][1]为1，dp[i][1]为1。
时间复杂度O（n）,空间复杂度O（n）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;int n;char man[100005][2][55];bool dp[100005][2];int num[100005];bool cmp(char s1[],char s2[]){for(int i=0;i<=50;i++){if(s1[i]&&s2[i]){if(s1[i]<s2[i])return 0;if(s1[i]>s2[i])return 1;}else{if(s1[i] && !s2[i])return 1;elsereturn 0;}}}bool ok(){for(int i=1;i<=n;i++){if(dp[i-1][0] && cmp(man[num[i]][0],man[num[i-1]][0])==1)dp[i][0]=1;if(dp[i-1][1] && cmp(man[num[i]][0],man[num[i-1]][1])==1)dp[i][0]=1;if(dp[i-1][0] && cmp(man[num[i]][1],man[num[i-1]][0])==1)dp[i][1]=1;if(dp[i-1][1] && cmp(man[num[i]][1],man[num[i-1]][1])==1)dp[i][1]=1;if(dp[i][0]==0 && dp[i][1]==0)return 1;}return 0;}int main(){dp[0][0]=dp[0][1]=1;cin>>n;for(int i=1;i<=n;i++)scanf("%s%s",man[i][0],man[i][1]);for(int i=1;i<=n;i++)scanf("%d",num+i);if(ok())printf("NO\n");elseprintf("YES\n");return 0;}
D Design Tutorial: Inverse the Problem
题目大意：
已知一个图中有n（1≤n≤2000）个点，给出一个n*n的矩阵d，d[i][j]表示点i和点j的最小距离（0≤d[i][j]≤10^9）,问是否存在一棵由这n个点组成的树，满足这个邻接矩阵。
解题思路：
首先对矩阵进行处理，得出n*（n-1）/2条边，同时如果矩阵不满足无向图邻接矩阵的特点，直接得出结果。
这些边从小到大排序，做生成树。因为原图是一棵树，所以不会有环，每对点之间的距离是唯一确定的。按从小到大排序后，如果之前选择的边不能将当前的点连接，那么连接当前这对点的边一定在树上，于是将当前边加入选择。最终选择出n-1条边。
以每个点为出发点分别跑一次dfs，得到所选树的邻接矩阵，与原邻接矩阵进行比对就可以得出结果。
用邻接表或者链式向前星储存树，否则dfs的时候可能会T。
时间复杂度O（log（n^2）*n^2）,空间复杂度O（n^2）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;struct Edge{int u,v;long long dis;friend bool operator <(Edge x1,Edge x2){return x1.dis<x2.dis;}};struct Edges{int v;long long dis;};vector <Edge> ev;vector <Edges> v[2005];queue <Edges> q;long long dis[2005][2005],ans[2005][2005];int n;int root[2005];int findr(int x){if(root[x]==x)return x;elsereturn root[x]=findr(root[x]);}bool ok1(){Edge temp;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){if(j==i){if(dis[i][j])return 1;}else{if(dis[i][j]!=dis[j][i] || !dis[i][j])return 1;else{temp.u=i;temp.v=j;temp.dis=dis[i][j];ev.push_back(temp);}}}}return 0;}void gg(){int lens=ev.size();Edges temp1,temp2;int x,y;for(int i=0;i<lens;i++){x=findr(ev[i].u);y=findr(ev[i].v);if(x!=y){root[x]=y;temp2.v=ev[i].u;temp1.v=ev[i].v;temp1.dis=temp2.dis=ev[i].dis;v[ev[i].u].push_back(temp1);v[ev[i].v].push_back(temp2);}}}void go(int x){Edges temp1,temp2;int now,nownums;temp1.v=x;temp1.dis=1;q.push(temp1);while(!q.empty()){temp1=q.front();q.pop();now=temp1.v;ans[x][now]=temp1.dis;nownums=v[now].size();for(int i=0;i<nownums;i++){temp2.dis=temp1.dis+v[now][i].dis;temp2.v=v[now][i].v;if(!ans[x][temp2.v])q.push(temp2);}}}bool ok2(){for(int i=1;i<=n;i++)for(int j=i;j<=n;j++){if(dis[i][j]+1!=ans[i][j])return 1;}return 0;}int main(){cin>>n;for(int i=1;i<=n;i++){root[i]=i;for(int j=1;j<=n;j++)scanf("%lld",&dis[i][j]);}if(ok1())printf("NO\n");else{sort(ev.begin(),ev.end());gg();for(int i=1;i<=n;i++)go(i);if(ok2())printf("NO\n");elseprintf("YES\n");}return 0;}
E MUH and Sticks
题目大意：
给出六个整数l（1<=li<=9），代表六根棍子的长度。有两种动物可以用棍子拼成：①熊：四根代表四肢的棍子长度相等，剩下两根中代表头的棍子比代表身体的棍子短；②大象：四根代表四肢的棍子长度相等，剩下两根中代表头的棍子和代表身体的棍子一样长。如果两种动物都不能拼成，则拼成“外星人”。问给出的六根棍子能拼成啥。
解题思路：
简单的条件判断，当某四根棍子长度相等的时候，四肢的长度就已经确定下来了，根据剩下两根棍子的长度确定是熊还是大象；否则只能拼成外星人。
时间复杂度O(1)，空间复杂度O(1)。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;int main(){int num[10];for(int i=0;i<6;i++)scanf("%d",num+i);sort(num,num+6);if(num[0]==num[3]){if(num[4]==num[5])printf("Elephant\n");elseprintf("Bear\n");}else{if(num[2]==num[5]){if(num[0]==num[1])printf("Elephant\n");elseprintf("Bear\n");}else{if(num[1]==num[4])printf("Bear\n");elseprintf("Alien\n");}}}
F MUH and Important Things
题目大意：
有N（1<=n<=2000）个任务,难度分别为h（1<=hi<=2000）,判断是否存在至少三种不同的序列，满足每种序列的难度不减，若存在输出其中任意三种符合条件的序列。
解题思路：
首先判断是否存在三种以上的序列：如果这n个数各不相同或其中仅有2个数相同，即n个数中有超过n-2种不同的数，则不存在三种以上满足要求的序列。
然后将这n个任务按照难度从小到大排序，难度相同的任务，序号更小的排在前面，构成第一种序列。
接着寻找序列中最早出现的连续两个难度相同的任务，交换它们构成第二种序列。
最后寻找序列中最晚出现的连续两个难度相同的任务，交换它们构成第三种序列。
由于数组中不同的数的种类不超过n-2种，所以至少有两组相邻的任务难度相同，所以第二种序列和第三种序列选择交换的那两对任务不会处于相同位置，也就保证了三种序列互不相同。
时间复杂度O(nlogn)，空间复杂度o（n）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;struct Task{int val,no;friend bool operator <(Task t1,Task t2){if(t1.val==t2.val)return t1.no<t2.no;elsereturn t1.val<t2.val;}}num[2005],temp;int n,nums=0;int life[2005];int flag1=-1,flag2=-1;int main(){cin>>n;for(int i=0;i<n;i++){scanf("%d",&num[i].val);if(!life[num[i].val])nums++;life[num[i].val]++;num[i].no=i+1;}if(nums<=n-2){printf("YES\n");sort(num,num+n);for(int i=0;i<n;i++){printf("%d ",num[i].no);if(flag1==-1 && num[i].val==num[i+1].val)flag1=i;if(num[i].val==num[i+1].val)flag2=i;}printf("\n");temp=num[flag1];num[flag1]=num[flag1+1];num[flag1+1]=temp;for(int i=0;i<n;i++)printf("%d ",num[i].no);printf("\n");temp=num[flag2];num[flag2]=num[flag2+1];num[flag2+1]=temp;for(int i=0;i<n;i++)printf("%d ",num[i].no);printf("\n");}elseprintf("NO\n");}
G MUH and House of Cards
题目大意：
用恰好n（1<=n<=10^12）张卡片搭建一个房子，问能搭建多少种不同的高度的房子。
搭建的房子满足以下要求：
1.每一层的房子数要多于他上面那层的房子数。
2.同一层的房子必须是连续的。
3.大于两间的房子要有天花板。
解题思路：
不难看出，若某一层有x个房子，则这一层要用掉3*x-1=3*（n-1）+2张卡片（x>0）。所以若n张卡片可以搭建y层的房子，首先（n-2*y）要是3的倍数，其次（n-2*y）/3足够从最底下的第1层搭到最高的第y层。可以预处理出搭到每一层需要的最少的额外房间数（其实就是累和）,即可快速判断n是否能搭成y层的房子。
经过周（暴）密（力）计（打）算（表），最多能搭的层数不超过1500000，于是时间复杂度o（sqrt（n）），空间复杂度o（sqrt（n））。
吐槽：这题居然不多组，白打了一个表。。。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;long long num[1500005];int main(){for(int i=1;i<=1500000;i++)num[i]=num[i-1]+i;long long n,ans=0;cin>>n;for(int i=0;i<=1500000;i++){if((n-2LL*(i+1))%3==0 && (n-2LL*(i+1))/3>=num[i])ans++;}printf("%lld\n",ans);return 0;}
H MUH and Cube Walls
题目大意：
给定两个整数n和w（1<=n,w<=2*10^5），接下来n个整数a（1<=ai<=10^9）描述了长为n列的墙，和w个整数b（1<=bi<=10^9）描述了长为w列的“大象”，当墙的某一段和“大象”形状相同，即通过上下平移这段墙可以与大象完全重合，就算“see an elephant”。问能看到几只大象。
解题思路：
我们把每一列和它左边的那一列比较，得到一个长度-1的序列，这个序列就描述了这一段的形状，并且和实际高度无关，由此我们可以把这个问题转化为两个串的匹配，直接套kmp。
注意特判w为1和n为1的情况。
时间复杂度o（n），空间复杂度o（n）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;int l1,l2;int num1[200005],num2[200005];int nex[200005];int ans=0;void kmppre(int s[],int l){int i=0,j=-1;nex[0]=-1;while(i<l){while(j!=-1 && s[i]!=s[j]) j=nex[j];nex[++i]=++j;}}void kmp(int s1[],int len1,int s2[],int len2){kmppre(s1,len1);int i=0,j=0;while(i<len2){while(j!=-1 && s2[i]!=s1[j]) j=nex[j];j++;i++;if(j>=len1){ans++;j=nex[j];}}}int main(){cin>>l1>>l2;for(int i=0;i<l1;i++)scanf("%d",num1+i);l1--;for(int i=0;i<l1;i++)num1[i]=num1[i+1]-num1[i];for(int i=0;i<l2;i++)scanf("%d",num2+i);l2--;for(int i=0;i<l2;i++)num2[i]=num2[i+1]-num2[i];if(l1){if(l2)kmp(num2,l2,num1,l1);elseans=l1+1;}elseans=!l2;cout<<ans<<endl;return 0;}
I George and Accommodation
题目大意：
已知n（1<=n<=100）个房间的容量q和已入住人数p（0<=pi<=qi<=100），问有多少个房间能满足乔治和阿历克斯想住在一♂起的愿望。
解题思路：
遍历一遍，看有哪些房间剩余人数超过2个。
时间复杂度o（n），空间复杂度o（n）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;int main(){int n,ans=0;int a,b;cin>>n;while(n--){scanf("%d%d",&a,&b);if(a<b-1)ans++;}cout<<ans<<endl;return 0;}
J Fedor and New Game
题目大意：
有m（1<=m<=1000）个其他玩家和n(1<=n<=20)种兵种,接下来m个整数x（0<=xi<=2^n-1）描述了这m个玩家的兵种情况，一个整数X描述了主人公的兵种情况。
兵种情况的描述方式：以二进制考虑，第0到第n-1位分别表示该玩家是否拥有当前兵种。
给定k（1<=k<=n）,当两名玩家的兵种情况的差异不超过k，这两名玩家可以成为好朋友。问主人公可以和多少名玩家成为好朋友。
解题思路：
把每个玩家包括主人公的兵种情况，按二进制分解到二维数组中，然后暴力比较。
时间复杂度o（m*n），空间复杂度o（m*n）；
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;int nums[1005][25];int n,m,k;void go(int x,int now){for(int i=0;i<=n;i++){nums[now][i]=x%2;x/=2;}}int cmp(int x1,int x2){int ans=0;for(int i=0;i<=n;i++){if(nums[x1][i]!=nums[x2][i])ans++;}return ans;}int main(){cin>>n>>m>>k;int x;int ans=0;for(int i=0;i<=m;i++){scanf("%d",&x);go(x,i);}for(int i=0;i<m;i++){if(cmp(i,m)<=k)ans++;}cout<<ans<<endl;return 0;}
K George and Job
题目大意：
给定一个长度为n（1<=n<=5000）的整数序列p（0<=pi<=10^9），让你在序列p中选择不重合的m段长度为k的子段（1<=m*k<=n），求这m*k个数的和的最大值。
解题思路：
dp[i][j]表示到第i位为止，选择了j段的情况下的最大和。asksum（i，j）表示p[i]+p[i+1]+...+p[j]。
状态转移方程为：dp[i][j]=max(dp[i-1][j],dp[i-k][j-1]+asksum（i+1，j）)。其中asksum（i+1，j）可以用前缀和来求。sum[i]表示p[1]+p[2]+...+p[i],则asksum（i+1，j）=sum[j]-sum[i]。
注意边界条件和预处理。
时间复杂度o（n*m），空间复杂度o（n*m）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;long long sum[5005];long long dp[5005][5005];bool ok[5005][5005];int n,m,k;int main(){cin>>n>>m>>k;for(int i=1;i<=n;i++){scanf("%lld",sum+i);sum[i]+=sum[i-1];}ok[0][0]=1;for(int i=1;i<=n;i++){ok[i][0]=1;for(int j=1;j<=k;j++){dp[i][j]=dp[i-1][j];if(i>=m && ok[i-m][j-1]){ok[i][j]=1;dp[i][j]=max(dp[i][j],dp[i-m][j-1]+sum[i]-sum[i-m]);}}}cout<<dp[n][k]<<endl;return 0;}
L Fedor and Essay
题目大意：
给定由m（1<=m<=10^5）个单词组成的一篇文章，有n（0<=n<=10^5）对同义词，同义词之间可以互相代替任意次，求全文中字母'r'出现最少次数，以及该情况下最短的文章长度（字母数）。输入保证文章总长度不超过10^5，忽略大小写。
解题思路：
首先根据同义词的情况处理出一个无向图。
由题意可以看出r出现的次数更少要优先于单词长度，将所有单词按照这两个关键字和这个优先级排序，然后从最简的单词开始，每个单词把所有的比它复杂的同义词都转化为它自己。
最后按顺序输出文章中每个单词的最简形式。
时间复杂度o（(m+n)log(m+n)），空间复杂度o（n+m）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;map <string,int> mp;struct Node{string s;int r,num;}snode[300005];bool cmp(int a,int b){if(snode[a].r==snode[b].r){if(snode[a].num==snode[b].num)return a<b;elsereturn snode[a].num<snode[b].num;}elsereturn snode[a].r<snode[b].r;}int gg[300005];int n,m,nums=0;string temp,t1,t2;int num[100005];int dp[300005];vector <int> v[300005];void ok(string *x){int l=(*x).size();for(int i=0;i<l;i++){if((*x)[i]<='Z' && (*x)[i]>='A')(*x)[i]=(*x)[i]-'A'+'a';}}void solve(int x,string *s){mp[(*s)]=x;snode[x].s=(*s);snode[x].r=0;int l=(*s).size();snode[x].num=l;for(int i=0;i<l;i++){if((*s)[i]=='r')snode[x].r++;}}void go(int now,int x){if(!dp[now]){dp[now]=x;int l=v[now].size();for(int i=0;i<l;i++)go(v[now][i],x);}}int main(){cin>>n;for(int i=0;i<n;i++){cin>>temp;ok(&temp);if(mp[temp]==0){gg[nums]=nums+1;nums++;solve(nums,&temp);}num[i]=mp[temp];}int x,y,z;long long ans1=0,ans2=0;cin>>m;while(m--){cin>>t1>>t2;ok(&t1);if(mp[t1]==0){gg[nums]=nums+1;nums++;solve(nums,&t1);}ok(&t2);if(mp[t2]==0){gg[nums]=nums+1;nums++;solve(nums,&t2);}x=mp[t1];y=mp[t2];v[y].push_back(x);}sort(gg,gg+nums,cmp);for(int i=0;i<nums;i++)go(gg[i],gg[i]);for(int i=0;i<n;i++){num[i]=dp[num[i]];ans1+=snode[num[i]].r;ans2+=snode[num[i]].num;}printf("%lld %lld\n",ans1,ans2);return 0;}
M Cheap Travel
题目大意：
有两种地铁票，一种价格为a（1<=a<=1000）可以搭乘1次地铁，一种价格为b（1<=b<=1000）可以搭乘m（1<=m<=1000）次地铁，问：如果要搭乘n（1<=n<=1000）次地铁，最少花多少钱？
解题思路：
有三种方案：①买n张第一种票；②每m次搭乘买一张第二种票，剩下的次数买第一种票；③全买第二种票。算出三种方案的代价，取最小的为答案。
时间复杂度o（1），空间复杂度o（1）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;int main(){int ans;int n,m,a,b;cin>>n>>m>>a>>b;ans=a*n;ans=min(ans,(n%m)*a+(n/m)*b);ans=min(ans,(n/m+1)*b);cout<<ans<<endl;return 0;}
N Wonder Room
题目大意：
有一个a*b（1<=a，b<=10^9）大小的房间，通过增大a和b来改变房间的面积，使房间的面积不小于6*n（1<=n<=10^9），求满足条件的最小房间面积和改变后的a、b。
解题思路：
因为n<=10^9，所以6*n<=10^9，所以a和b中较小的那条边，不会超过sqrt（6*n）。枚举较小的那条边，算出另一条边应有的长度，然后算出面积，记录最小的。
注意特判一开始就满足条件的情况。另外要注意判断最后的a和b的顺序要和初始的一样。
时间复杂度o（sqrt（6*n）），空间复杂度o（1）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;int main(){bool flag=0;long long a,b,n,now,temp,gg,x,y;cin>>n>>a>>b;now=a*b;n*=6;if(a>b){temp=a;a=b;b=temp;flag=1;}x=a;y=b;if(now<n){for(temp=a-1;temp*temp<n;){temp++;gg=n/temp+(n%temp!=0);gg=max(gg,b);if(temp*gg<now || now<n){now=temp*gg;x=temp;y=gg;}}}if(flag && (x<b || y<a)){temp=x;x=y;y=temp;}printf("%lld\n%lld %lld\n",x*y,x,y);return 0;}
O Number of Ways
题目大意：
给定一个长度为n（1<=n<=5*10^5）的数列a（|ai|<=10^9），问有多少种办法把数列分为三段，每段至少包含一个数，并且每段的和相等。
解题思路：
如果数列a能被分成三段，那么它的和sum应该是3的倍数，并且第一段的和是sum/3，第一段和第二段的和为sum*2/3。用num1表示到目前为止，前缀和为sum/3的节点个数。于是每当前缀和为sum*2/3时，当前的sum1就表示以当前点为第二段的结尾，第一段结尾的可选方案数，将这个方案数加入答案。对数列依次求前缀和的同时维护num1和答案。
注意要先维护答案再维护num1，因为第一段的结尾和第二段的结尾不能重合。并且前缀和只能求到前n-1项，因为第三段的结尾已经固定为数列的最后一项，第二段的结尾不能和第三段的结尾重合。
时间复杂度o（n），空间复杂度o（n）。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queueusing namespace std;long long num[500005],sum=0,now=0;int n;int main(){long long num1=0,num2=0;cin>>n;for(int i=0;i<n;i++){scanf("%lld",num+i);sum+=num[i];}if(sum%3==0){for(int i=0;i<n-1;i++){now+=num[i];if(i && now==(sum/3)*2)num2+=num1;if(sum/3==now)num1++;}}cout<<num2<<endl;return 0;}
P Increase Sequence
题目大意：
给出一个长度为n（1<=n<=2000）的数列a（0<=ai<=2000），你可以选择其中任意段令这一段数分别加一，但是每一段只能操作一次，并且一个数不会同时作为两个段的开始或者两个段的结束。问将数列的每一项都变成h（1<=h<=2000）的方案总数。
解题思路：
每个位置只有四种情况：①作为某一段的开始；②作为某一段的结束；③既作为某一段的开始，又作为某一段的结束；④啥也不干。
用dp[i][j]表示到第i位位置，前i个数全部变为h，同时还有j个段有头无尾的情况的方案数，状态转移方程为：
1.当a[i]=h，dp[i][0]=dp[i-1][0]；
2.当a[i]>h，无解，方案数直接为0；
3.当a[i]<h:
dp[i][h-a[i]]=dp[i][h-a[i]]+dp[i][h-a[i]-1]（原本就有h-a[i]个头或当前新增一个头）
dp[i][h-a[i]-1]=（h-a[i]）*（dp[i][h-a[i]]+dp[i][h-a[i]-1]）（原本就有h-a[i]个头或当前新增一个头后，给其中某个头一个结尾）
dp[n][0]即为答案。
时间复杂度o（n），空间复杂度o（n^2）。
AC代码：
#include<iostream>#include<bits/stdc++.h>using namespace std;#define MOD 1000000007int num[2005],n,h;long long now[2005];long long dp[2005][2005];long long ask(){for(int i=1;i<=n;i++){if(num[i]>h)return 0;now[i]=1LL*(h-num[i]);}dp[0][0]=1;for(int i=1;i<=n;i++){if(now[i]){dp[i][now[i]]=(dp[i-1][now[i]]+dp[i-1][now[i]-1])%MOD;dp[i][now[i]-1]=(now[i]*(dp[i-1][now[i]]+dp[i-1][now[i]-1]))%MOD;}elsedp[i][now[i]]=dp[i-1][now[i]];}return dp[n][0];}int main(){cin>>n>>h;for(int i=1;i<=n;i++)scanf("%d",num+i);printf("%lld\n",ask());return 0;}