【JZOJ1282】打工

题目

分析

显然，有一个结论，
在有效的方案中，第i位的数一定小于等于i。
所以，设(f_{i,j,k})表示，做到第i位，前i位的最大值为j，前i位是否与输入的序列的前i位相等。
转移方程随便搞搞就OK了

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=2147483647;
const long long mo=1000007;
const int N=10005;
using namespace std;
int n,m,a[N],mx[N];
long long f[2][N][2],k;
long long max(long long x,long long y)
{
	if(x<y) return y;else return x;
}
long long min(long long x,long long y)
{
	if(x>y) return y;else return x;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		mx[i]=max(mx[i-1],a[i]);
	}
	f[0][1][1]=1;
	k=1;
	int q=1,p=0,j;
	for(int i=2;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
			f[q][j][1]=0;
			f[q][j][0]=((f[p][j][0]+f[p][j][1])*min(a[i]-1,j)+f[p][j][0]*max(0,j-a[i]+1)+f[p][j-1][0])%mo;
			if(j<a[i]) f[q][j][0]=f[q][j][0]+f[p][j-1][1];
		}
		f[q][mx[i]][1]=1;
		p=1-p;
		q=1-q;
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
		ans+=f[1-n%2][i][0]+f[1-n%2][i][1];
	cout<<ans%mo<<endl;
}