826-div3-e-dp

这个题的 dp 自己想想不出来，可能是因为做的题少了

Problem - E - Codeforces

题意大概是对于给定的序列 b ，能否构造一个序列 a 使得

a 被分成若干段到 b 中，每段的长度在 b 中记在此段的左边或右边 

定义状态表示为： 表示能否合法的走到第 i 个位置，值为1代表能，值为0代表不能。

大概思路是：将置为1，枚举它为一个“长度数”还是一个a数组的数，往后递推每一个合法状态，直到走到 n。只要一个状态能到 n 就为yes， 所以用 | 运算，任意一个为真则为真

#include
#includeusing namespace std;
const int N = 200010;
int b[N];
int f[N];int main()
{int t;cin >> t;while(t --){memset(f,0,sizeof f);int n;cin >> n;for(int i = 1; i <= n; i ++){cin >> b[i];}f[0] = 1;for(int i = 1; i <= n; i ++){if(i > b[i])//长度数 f[i] |= f[i - b[i] - 1];if(i + b[i] <= n)f[i + b[i]] |= f[i - 1]; }if(f[n])cout << "YES" << endl;elsecout << "NO" << endl; }
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！