程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj1996【HNOI2010】chorus 合唱隊

bzoj1996【HNOI2010】chorus 合唱隊

編輯:關於C++

Description

\

Input

\

Output

\

Sample Input

4
1701 1702 1703 1704

Sample Output

8

HINT

\

Source

f[i][j][0]和f[i][j][1]分別表示從i到j,最後一個從前和從後加入的方案數,然後就可以DP了。(轉移方程詳見程序)

注意i=j和i+1=j的特殊情況。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 2005
#define mod 19650827
using namespace std;
int n;
int a[maxn],f[maxn][maxn][2];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();
	F(i,1,n) a[i]=read();
	memset(f,0,sizeof(f));
	F(i,1,n) f[i][i][0]=f[i][i][1]=1;
	D(i,n-1,1) F(j,i+1,n)
	{
		if (i+1==j)
		{
			if (a[i]a[i]) (f[i][j][1]+=f[i][j-1][0])%=mod;
		if (a[j]>a[j-1]) (f[i][j][1]+=f[i][j-1][1])%=mod;
	}
	printf("%d\n",(f[1][n][0]+f[1][n][1])%mod);
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved