【HNOI2010】合唱队 – 徐亦轲的博客

明天就是入学考试了。。

虽然寒假一点学科都没搞，但是一点都不想复习呢。。

明天要跪烂了。。不管了

刷刷水题

一个简单的区间动规，从目标队形往回推，dp[l][r][k]表示[l,r]中最后一个人从第k边加入的方案数

// <chorus.cpp> - 02/27/16 04:07:33
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int mod=19650827;
const int MAXN=1001;
int dp[MAXN][MAXN][2];
int h[MAXN];
int main(){
	freopen("chorus.in","r",stdin);
	freopen("chorus.out","w",stdout);
	int n=getint();
	for(int i=1;i<=n;i++)h[i]=getint(),dp[i][i][0]=1;
	for(int i=n-1;i>=1;i--)
		for(int j=i+1;j<=n;j++){
			if(h[i]<h[i+1])dp[i][j][0]=(dp[i][j][0]+dp[i+1][j][0])%mod;
			if(h[i]<h[j])dp[i][j][0]=(dp[i][j][0]+dp[i+1][j][1])%mod;
			if(h[j]>h[j-1])dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][1])%mod;
			if(h[j]>h[i])dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][0])%mod;
		}
	printf("%d",(dp[1][n][0]+dp[1][n][1])%mod);
	return 0;
}

// <chorus.cpp> - 02/27/16 04:07:33

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int mod=19650827;

const int MAXN=1001;

int dp[MAXN][MAXN][2];

int h[MAXN];

int main(){

freopen("chorus.in","r",stdin);

freopen("chorus.out","w",stdout);

int n=getint();

for(int i=1;i<=n;i++)h[i]=getint(),dp[i][i][0]=1;

for(int i=n-1;i>=1;i--)

for(int j=i+1;j<=n;j++){

if(h[i]<h[i+1])dp[i][j][0]=(dp[i][j][0]+dp[i+1][j][0])%mod;

if(h[i]<h[j])dp[i][j][0]=(dp[i][j][0]+dp[i+1][j][1])%mod;

if(h[j]>h[j-1])dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][1])%mod;

if(h[j]>h[i])dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][0])%mod;

}

printf("%d",(dp[1][n][0]+dp[1][n][1])%mod);

return 0;

}

说点什么