[AHOI1997]彩旗飘飘

www.rqnoj.cn/Problem_371.html
这道题其实很简单,但我WA了2次。。原因是搞不清楚边界条件。。
实际上往后推的方便多了囧。。一下就AC。。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxn=15+10;
using namespace std;
typedef long long ll;
ll Dp[maxn][maxn][maxn][2]={};
int main()
{
//freopen("in","r",stdin);
int n,m;cin>>n>>m;
Dp[1][0][0][0]=Dp[0][1][0][1]=1;
for(int l=1;l<n*2;l++)
for(int a=0;a<=min(l,n);a++)
{
int b=l-a;
for(int c=0;c<=m;c++)
for(int l=0;l<2;l++)
if(ll x=Dp[a][b][l])
{
Dp[a+1][b][0]+=x;
Dp[a][b+1][1]+=x;
}
}
cout<<Dp[n][n][m][0]*2<<endl;
}

Leave a Reply

Your email address will not be published. Required fields are marked *