낙곡P3205 [HNOI2010] 합창단(구간dp)
전송문
문제풀이의 방향
대형의 구성 방식을 관찰하면 꼴찌가 구간 i에 가입하는 것을 알 수 있다.j의 사람은 i의 위치에 있거나 j의 위치에 있기 때문에 우리는 dp[i][j][0]로 구간 i를 표시할 수 있다.j 마지막으로 가입한 사람이 i 위치에 서 있는 방안의 총수는 같은 이치로 dp[i][j][1]로 구간 i...제이가 마지막으로 가입한 사람이 제이의 위치에 서 있는 방안의 총수.
그리고 상황에 따라 토론하면 된다.
마지막 답안은 dp[1][n][0]+dp[1][n][1]과 같다.
모든 조작에 대해 남은 것을 찾는 것을 잊지 마라.
AC 코드
1 #include
2 using namespace std;
3 int n,dp[1005][1005][2],a[1005];
4 const int mod=19650827;
5 int main()
6 {
7 cin>>n;
8 for(int i=1;i<=n;i++){
9 cin>>a[i];
10 dp[i][i][0]=dp[i][i][1]=1;
11 }
12 for(int i=1;i<=n;i++){
13 int j=i+1;
14 if(j>n) break;
15 if(a[i]0]=dp[i][j][1]=1;
16 }
17 for(int len=3;len<=n;len++){
18 for(int i=1;i<=n;i++){
19 int j=i+len-1;
20 if(j>n) break;
21 if(a[i]1]){
22 dp[i][j][0]+=dp[i+1][j][0];
23 }
24 if(a[i]<a[j]){
25 dp[i][j][0]+=dp[i+1][j][1];
26 }
27 if(a[j]>a[i]){
28 dp[i][j][1]+=dp[i][j-1][0];
29 }
30 if(a[j]>a[j-1]){
31 dp[i][j][1]+=dp[i][j-1][1];
32 }
33 dp[i][j][0]%=mod;
34 dp[i][j][1]%=mod;
35 }
36 }
37 cout<1][n][0]+dp[1][n][1])%mod;
38 return 0;
39 } 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
