Codeforces Round #826 (Div. 3) E. Sending a Sequence Over the Network
The Codeforces div round Network sequence Over
2023-09-11 14:14:52 时间
题意:
给定一个数组,将该数组分成连续的若干部分。每一部分的长度大小是该部分最左端或者最右端的大小-1,求能否将这个数组完全分成合法的若干部分。
思路:
考虑dp
状态设计:设dp[i]表示到第i个位置是否能合法
状态转移:
枚举决策,发现这次遍历到的a[i]可以作为左侧值也可以作为右侧值,如果作为左侧值,那么dp[i+a[i]]由dp[i-1]转移过来,如果作为右侧值,那么dp[i]由dp[i-a[i]-1]转移过来
Code:
#include <bits/stdc++.h>
using namespace std;
const int mxn=2e5+10;
#define int long long
int n;
int a[mxn],dp[mxn];
void solve(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],dp[i]=0;
dp[0]=1;
for(int i=1;i<=n;i++){
if(i+a[i]<=n) dp[i+a[i]]|=dp[i-1];
if(i-a[i]>=1) dp[i]|=dp[i-a[i]-1];
}
if(dp[n]) cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--)solve();
return 0;
}
相关文章
- Go语言圣经 《The Go Programming Language》 中文版本
- Timeout expired. The timeout period elapsed prior to completion of the operation or the server is not responding.
- 报错:hadoop There appears to be a gap in the edit log. We expected txid 927, but got txid 1265.
- 【CF438E】The Child and Binary Tree(多项式运算,生成函数)
- Codeforces Round #820 (Div. 3) D. Friends and the Restaurant
- The platform of the target `Pods` (iOS 4.3) is not compatible 错误
- Google Earth Engine(GEE)——The bands of the specified image contains different projections
- Timeout expired. The timeout period elapsed prior to completion of the operation or the server is not responding.
- The connection to the server localhost:8080 was refused - did you specify the right host or port?
- CodeForces 732B Cormen — The Best Friend Of a Man (贪心)
- CodeForces 288B Polo the Penguin and Houses (暴力或都快速幂)
- ERROR: The Python ssl extension was not compiled. Missing the OpenSSL lib?
- 【CodeForces 618B】Guess the Permutation
- 金仓kingbase连接报错The authentication type 10 is not supported. Check that you have configured the sys_hba.conf file to include the client's IP address or subnet
- Unity 报错之 The same field name is serialized multiple times in the class or its parent class.
- The 10 Most Important Security Controls Missing in JavaEE--reference
- 无状态配置报错:Session creation has been disabled for the current subject