bzoj 1996 (구간 dp)

1109 단어 dp
전송문 문제풀이: dp[i][j][0/1]를 설정하여 현재 구간 [i, j]에 마지막으로 a[i]/a[j]를 추가하여 이상적인 대기열을 구성하는 방안수를 나타낸다.이렇게 하면 되는 이유: 지난번에 추가된 수는 반드시 양쪽에 나타나기 때문에 양쪽과 직접 비교하면 된다.지능이 낮은 아이는 오랫동안 생각했다.
/*  :      a[i]#include
using namespace std;
const int MAXN=1002,MOD=19650827;
int n,dp[MAXN][MAXN][2],a[MAXN];
int main() {
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
for (int i=1;i<=n;++i) dp[i][i][0]=1;
for (int i=n-1;i;--i)
for (int j=i+1;j<=n;++j) {
if (a[i]1]) dp[i][j][0]+=dp[i+1][j][0];
            if (a[i]0]+=dp[i+1][j][1];
if (a[j]>a[j-1]) dp[i][j][1]+=dp[i][j-1][1];
if (a[j]>a[i]) dp[i][j][1]+=dp[i][j-1][0];
dp[i][j][0]%=MOD,dp[i][j][1]%=MOD;
}
printf("%d",(dp[1][n][0]+dp[1][n][1])%MOD);
return 0;
}

좋은 웹페이지 즐겨찾기