牛客小白月赛88补题D

D-我不是大富翁

题意：

做法：一开始是往贪心方面想，但是很明显，贪不了。又因为走的步先后顺序没影响，可以用dp来写。暴力也差不多。

值得注意的点是动力序列可以一边读入一边处理，省了点空间。

如果dp[5005][5005]这样开的话会MLE，实际上在dp的过程中，用到的只是i和i-1两行，其余都是多余的。

所以可以这样定义dp[2][5005]这样可以避免MLE；

还有就是要特判n==1的情况。

//int dp[5005][5005];  //--MLE
int dp[2][5005];  //优化空间！！！                  wa--5 1 0
//dp[i][j]定义为，到了第i步,可以到达j哪些格子。
//暴力差不多--遍历m步.每步遍历n，看看可以到达哪些格子.看看最后一步是否可以到达1.

void solve(){           //D
    int n,m,x;
    cin>>n>>m;
    if(n==1){               //特判！！
        cout<<"YES";
        return;
    }
    dp[0][1]=1;
    for(int i=1;i<=m;i++){
        cin>>x;
        x%=n;
        for(int j=1;j<=n;j++){
            if(dp[(i+1)%2][j]){
                    dp[(i+1)%2][j]=0;
                    dp[i%2][(j+x)%n]=1;
                    dp[i%2][(j-x+n)%n]=1;
            }
        }
    }
    if(dp[m%2][1]) cout<<"YES";
    else cout<<"NO";
}

在写的时候加了个条件判断x==0的情况，但是实际上x==0的情况是相同处理的，不用特别处理。