首页 > 代码库 > 动态规划入门 TYVJ1305 最大子段和(环状)
动态规划入门 TYVJ1305 最大子段和(环状)
TYVJ挂了???
没听懂大巨讲的什么窗口滑动,只好自己瞎造一个了......
贴代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 int n,m; 8 int head,tail; 9 int in; 10 int sum,ans; 11 int num[300010],pos[300010]; 12 13 int main(){ 14 scanf("%d%d",&n,&m); 15 head=1; 16 tail=2; 17 for(int i=1;i<=n;i++){ 18 scanf("%d",&in); 19 sum+=in; 20 while(num[tail-1]>=sum&&tail>head) tail--; 21 num[tail]=sum; 22 pos[tail]=i; 23 tail++; 24 while(i-pos[head]>m) head++; 25 ans=max(ans,sum-num[head]); 26 } 27 printf("%d\n",ans); 28 return 0; 29 }
动态规划入门 TYVJ1305 最大子段和(环状)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。