首页 > 代码库 > 玲珑oj 1121 思维
玲珑oj 1121 思维
1121 - Reverse the lights
Time Limit:2s Memory Limit:256MByte
Submissions:376Solved:111
DESCRIPTION
有n
个灯,初始时都是不亮的状态,每次你可以选择一个某一个灯,不妨记为x,所有满足和x距离不超过k的灯的状态都将被翻转,选择第i个灯的代价记为ci
,问最终所有灯都是亮的状态的最小花费.
INPUT
输入有两行,第一行包含两个正整数n(1≤n≤10000)和k(0≤k≤1000)
第二行包含n个整数,分别表示ci(0≤ci≤109)
OUTPUT
输出一行表示答案
SAMPLE INPUT
3 1 1 1 1
SAMPLE OUTPUT
1
一开始思路还是对的,可惜一直想怎么dp,最后发现不需要dp,直接扫描一次求最优解就好了。
每个灯最多只开一次,多开也没用,开了又关相当于没起到作用,我们只要依次枚举第一个开的地点,他所达到的范围内的灯就都不用开了,
直接跳到最近的一个处于关闭状态的灯前开启这个灯即可。
如果我们不这么做的话,那么两盏开启的灯之间就会出现重叠部分而抵消,为了处理这些重叠我们需要再开一些灯这样又会出现更多的重叠。
具体的证明,我也没证出来,但是感觉一下确实是这样子的。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int n,k,i,j; 6 long long ans=1e18,c[10005]; 7 cin>>n>>k; 8 for(i=1;i<=n;++i) cin>>c[i]; 9 if(!k) {ans=0;for(i=1;i<=n;++i)ans+=c[i];n=-999; } 10 for(i=1;i<=n;++i) 11 { 12 int s=i,e=n-k,x=s; 13 long long p=0; 14 if(s-k>1) break; 15 for(j=s;j<=n;j+=(2*k)+1) { 16 p+=c[j]; 17 x=j; 18 } 19 if(x+k>=n) {ans=min(ans,p);} 20 } 21 cout<<ans<<endl; 22 return 0; 23 }
玲珑oj 1121 思维
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。