首页 > 代码库 > 黑书例题 Fight Club 区间DP

黑书例题 Fight Club 区间DP

2024-07-15 18:50:44   214人阅读

题目可以在bnuoj、soj等OJ上找到。

题意：

不超过40个人站成一圈，只能和两边的人对战。给出任意两人对战的输赢，对于每一个人，输出是否可能是最后的胜者。

分析：

首先序列扩展成2倍，破环成链。

dp[i][j]表示i和j能够相遇对打，那么dp[i][i+n]为真代表可以成为最后胜者。

枚举中间的k，若i和j都能和k相遇，且i和j至少一人能打赢k，那么i和j可以相遇。

复杂度o(n^3)

 

 1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4  5 int T, n; 6 int b[100][100]; 7 bool dp[100][100]; 8 int main() 9 {10     scanf("%d", &T);11     while(T--)12     {13         scanf("%d", &n);14         for (int i = 1; i <= n; i++)15             for (int j = 1; j <= n; j++){16                 scanf("%d", &b[i][j]);17                 //if (i == j) b[i][j] = 1;18                 b[i+n][j] = b[i][j+n] = b[i+n][j+n] = b[i][j];19             }20         memset(dp, false, sizeof(dp));21         for (int i = 1; i <= 2*n; i++) dp[i][i] = true;22         for (int i = 1; i < 2*n; i++) dp[i][i+1] = dp[i+1][i] = true;23         for (int l = 1; l <= n; l++)24             for (int i = 1; i <= n; i++){25                 int j  = i + l;26                 if (j > 2*n) break;27                 for (int k = i+1; k < j; k++)28                     if (dp[i][k] && dp[k][j] && (b[i][k] || b[j][k]))29                         //if (dp[i][k] && dp[k+1][j] && b[i][k] && b[j][k+1])　　//这样写是错的，改了很久，加了很多条件也改不对30                         dp[i][j+n] = dp[i+n][j] = dp[i+n][j+n] = dp[i][j] = true;31             }32         for (int i = 1; i <= n; i++)33             if (dp[i][i+n]) printf("1\n");34             else printf("0\n");35         printf("\n");36     }37     return 0;38 }

 


联系
我们