递推DP 赛码 1005 Game

题目传送门

 /*
递推DP:官方题解
令Fi,j代表剩下i个人时,若BrotherK的位置是1,那么位置为j的人是否可能获胜
转移的时候可以枚举当前轮指定的数是什么,那么就可以计算出当前位置j的人在剩下i − 1个人时的位置
(假设BrotherK所处的位置是1),然后利用之前计算出的F值判定此人是否可能获胜
时间复杂度为O(n3)
dp[i][j] 表示有i个人,j位置的人是否可能胜利。dp[1][0] = 1; cnt = sum (dp[n][i]);
有最优化子结构,i个人可以由i-1个人的情况中每个能胜利的位置再走一步
取余小技巧:0~n-1
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <cmath>
#include <queue>
using namespace std; const int MAXN = 2e2 + ;
const int INF = 0x3f3f3f3f;
int dp[MAXN][MAXN];
int s[MAXN]; int main(void) //赛码 1005 Game
{
//freopen ("E.in", "r", stdin); int t, n, m;
scanf ("%d", &t);
while (t--)
{
scanf ("%d%d", &n, &m);
for (int i=; i<=m; ++i)
{
scanf ("%d", &s[i]);
}
memset (dp, , sizeof (dp));
dp[][] = ; for (int i=; i<=n; ++i)
{
for (int j=; j<n; ++j)
{
if (dp[i-][j])
{
for (int k=; k<=m; ++k)
{
dp[i][(j + s[k]) % i] = ;
}
}
}
} int cnt = ;
for (int i=; i<n; ++i) if (dp[n][i]) cnt++; printf ("%d\n", cnt); int x = ;
for (int i=; i<n; ++i)
{
if (dp[n][i])
{
printf ("%d", i + ); ++x;
if (x < cnt) printf (" ");
}
}
puts ("");
} return ;
}
上一篇:阿里云API网关(11)外网访问 阿里云API网关内定义的API步骤:


下一篇:C#_简单实用的翻页