鞍山+网站建设,网站架构建设,网站建优化,晋江住房和城乡建设局网站原题
首先记录这一道题的目的是提醒自己#xff1a;动态规划的属性并不是只有 m a x max max#xff0c; m i n min min 和 c o u n t count count#xff0c;同时还有布尔类型的dp
这题不能考虑在距离的维度上思考#xff0c;比如说看走几步走到哪里了#xff0c;如果… 原题
首先记录这一道题的目的是提醒自己动态规划的属性并不是只有 m a x max max m i n min min 和 c o u n t count count同时还有布尔类型的dp
这题不能考虑在距离的维度上思考比如说看走几步走到哪里了如果这么想根本无法下手进行dp 所以我们考虑的是能不能到达某一个点。
这里使用f[i][j]代表在前i步时能不能有一种走法到达 j 1 j1 j1点如果直接表示能否到达 j j j点会导致边界错误。
那么集合就只能被划分为能到达和不能到达。
能到达时上一层的状态就必须满足能够在第i步通过某种方式走到j1点注意这里很猪鼻的一点我们是从j的前后转移来的所以上一层的状态是 f [ i − 1 ] [ j a [ i ] ] f[i-1][ja[i]] f[i−1][ja[i]]和 f [ i − 1 ] [ j − a [ i ] ] f[i-1][j-a[i]] f[i−1][j−a[i]]但是如果这里直接用j-a[i]来表示元素会导致数组越界因为会减成负数所以这里应该用 f [ i − 1 ] [ ( j − a [ i ] n ) f[i-1][(j-a[i]n) f[i−1][(j−a[i]n)% n ] n] n]来表示状态。并且用 j − a [ i ] j-a[i] j−a[i]也会出错因为会走到一个不在环里面的地方所以要用 ( j − a [ i ] ) (j-a[i])%n (j−a[i])什么你问我为什么 ( j − a [ i ] n ) (j-a[i]n) (j−a[i]n)% n n n和j-a[i]能表示一种状态因为这里要走的格子是一个环状的呀。
代码
#includeiostream
#includealgorithm
using namespace std;
const int N 5010;
int a[N];
bool f[10000][10000];
int main(){int n,m;cin n m;long long sum 0;for(int i 1;i m;i){cin a[i]; a[i] % n; //这里直接取模数不然出错}f[0][0] 1;//第0步没走,当然就站在1各格子上for(int i 1;i m;i){for(int j 0;j n;j){f[i][j] ((f[i-1][(j-a[i]n)%n] 1) || (f[i-1][(ja[i])%n] 1) ); }}if(f[m][0] 1)cout YES;else cout NO;return 0;
}
