[Sdoi2010 地精部落]动态规划

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1925
【算法分析】
F[i][j][k]表示第i段，小于当前选择的那个数的个数是j，k代表是下一个该上升还是下降，的方案数。
然后转移就行了。
然后需要用滚动数组优化。
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【CODE】
#include #include #include #include using namespace std;
const int N=4205;
int n,mod;
int F[2][N][2];

void dp(){
int i,j,k,p,rest,Sum;
memset(F,0,sizeof(F));
for (i=0;i for (i=2;i<=n;i++){
p=i%2; rest=n-i;
for (j=0;j<=rest;j++){
F[p][j][0]=0;
F[p][j][1]=0;
}
// Deal up
Sum=0;
for (j=0;j<=rest;++j){
Sum+=F[1-p][j][1]; if (Sum>=mod) Sum%=mod;
F[p][j][0]=Sum;
}
// Deal down
Sum=F[1-p][rest+1][0];
for (j=rest;j>=0;–j){
F[p][j][1]=Sum;
Sum+=F[1-p][j][0]; if (Sum>=mod) Sum%=mod;
}
}
Sum=0;
for (i=0;i<=rest;i++){
Sum+=F[p][i][0]; if (Sum>=mod) Sum%=mod;
Sum+=F[p][i][1]; if (Sum>=mod) Sum%=mod;
}
cout << Sum << endl;
}

int main(){
cin >> n >> mod;
if (n==1) cout << 1 % mod << endl;
else dp();
}