낙곡P2051 중국 장기【dp】

8176 단어
제목:https://www.luogu.org/problemnew/show/P2051
제목: n*m의 칸에서 포를 쏘아 서로 공격할 수 없게 한다.
만약 두 포가 같은 줄에 같은 열이고 중간에 바둑알이 하나 더 있다면 공격할 수 있다.대포를 쏘는 방안이 몇 가지가 있느냐고 물었다.
사고방식: 우선 규칙에 따라 임의의 행과 열중포를 내놓을 수 있는 개수는 2개를 초과해서는 안 된다.
밀어냄을 시도해 볼 수 있습니다.$dp[i][j][k]$는 $i$줄로 처리되었음을 나타냅니다. 한 개의 포만 $j$개, 두 개의 포가 $k$개로 처리되었을 때의 방안 수입니다.
$i-1$행이 $i$를 처리했을 때 0, 1, 2개의 포를 쏘아올릴 수 있습니다.
그래서 $dp[i][j][j][j][k] = dp[i-1] [j][ii][i-1] [j1] [j] [j] [j] [j] [j][i-1] [j] + dp[i-1] [j-1] [j-1] [j-1] [j-1] [j] [k] * (m-j-k + 1) + dp[i- 1] [j[i-1] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [k] [k] = = = = = = [k- 1] [i-1] [i-1] [i-1] [i] [i] [i] [i] (m-j-k+1)$[이렇게 할 때마다 누가 누구를 밀어냈는지 헷갈린다.]
중간 과정에 int가 터질 수 있으니 LL로 하세요.
 1 #include
 2 #include
 3 #include
 4 #include<set>
 5 #include
 6 #include
 7 #include
 8 #include 
 9 #include
10 #include
11 #include
12 
13 #define inf 0x3f3f3f3f
14 using namespace std;
15 typedef long long LL;
16 typedef pair<int, int> pr;
17 
18 int n, m;
19 const int maxn = 105;
20 const LL mod = 9999973;
21 LL dp[maxn][maxn][maxn];
22 
23 int main()
24 {
25     scanf("%d%d", &n, &m);
26     dp[0][0][0] = 1;
27     for(int i = 1; i <= n; i++){
28         for(int j = 0; j <= m; j++){
29             for(int k = 0; j + k <= m; k++){
30                 dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % mod;
31                 if(j >= 1)dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k] * (m - j - k + 1)) % mod;
32                 if(k >= 1 && j + 1 <= m)dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j + 1][k - 1] * (j + 1)) % mod;
33                 if(j >= 2)dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 2][k] * ((m - j - k + 2) * (m - j - k + 1) / 2)) % mod;
34                 if(k >= 2 && j + 2 <= m)dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j + 2][k - 2] * ((j + 2) * (j + 1) / 2)) % mod;
35                 if(k >= 1)dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1] * j * (m - j - k + 1)) % mod;
36             }
37         }
38     }
39     
40     LL ans = 0;
41     for(int j = 0; j <= m; j++){
42         for(int k = 0; j + k <= m; k++){
43             ans = (ans + dp[n][j][k]) % mod;
44         }
45     }
46     printf("%lld
", ans);
47     return 0;
48 }

 
전재 대상:https://www.cnblogs.com/wyboooo/p/11107414.html
[정수리] [DP 확률 DP 앨범] [10, 4 최신 업데이트]
Gatsby의 wrapPageElement를 사용하여 여러 경로에서 지속적인 UI 유지

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage