一堆石头 取完最后一个的胜利 m种取法 完全背包变形 dp[i] = true表示先守取第i个可达 dp[n] = true先手胜 否则输
#include#include #include #include using namespace std; bool dp[1000001]; int n,m,a[11]; int main() { int i,j; while(scanf("%d",&n)!=EOF) { scanf("%d",&m); for(i = 0; i < m; i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); for(i = 1; i <= n; i++) { for(j = 0; j < m; j++) { if(i > = a[j] && !dp[i-a[j]]) { dp[i] = true; break; } } } if(dp[n]) printf("Stan wins\n"); else printf("Ollie wins\n"); } return 0; }