Codeforces Round #826 (Div. 3) E

E. Sending a Sequence Over the Network

题意：给定一个长度为 $m$ 的数组 $b$，判断是否能将该数组分成若干连续块，使得：1.$b$数组的每一个元素都恰好属于其中的一块，2.每一块的首元素或者尾元素=块的长度-1。
思路：DP
状态定义：
dp[i]:表示以i为结尾的是否能被合法分割
状态转移：
1.若dp[i-1]合法 且 i+a[i]<=n，那么dp[i+a[i]]也合法
2.若i-a[i]>=1 且 dp[i-a[i]-1]合法，那么dp[i]也合法
参考
记住记住！动态规划算法的核心就是记住已经解决过的子问题的解，由小问题推到大问题。

代码：

#include 
using namespace std;#define il inline
#define pb push_back
#define fi first
#define se second
#define int long long
#define pii pair<int,int>
const double PI=acos(-1.0);
const double eps=1e-6;
const int mod=1e7+7;
const int N=2e5+5;
const int inf=0x3f3f3f3f;int T,n,a[N],dp[N];signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;int cs=0;
//	T=1;while(T--){cin>>n;for(int i=1;i<=n;++i) cin>>a[i]; for(int i=0;i<=n;++i) dp[i]=0; dp[0]=1;for(int i=1;i<=n;++i){if(dp[i-1]==1 && i+a[i]<=n) dp[i+a[i]]=1;if(i-a[i]>=1 && dp[i-a[i]-1]==1) dp[i]=1;}if(dp[n]) cout<<"YES\n";else cout<<"NO\n";}
}

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