1121 - Reverse the lights（翻转问题）

题目链接：http://www.ifrog.cc/acm/problem/1121

1121 - Reverse the lights

Time Limit：2s Memory Limit：256MByte

Submissions：312Solved：93

DESCRIPTION

有$n$个灯，初始时都是不亮的状态，每次你可以选择一个某一个灯，不妨记为$x$，所有满足和$x$距离不超过$k$的灯的状态都将被翻转，选择第$i$个灯的代价记为$c_i$，问最终所有灯都是亮的状态的最小花费.

INPUT 输入有两行，第一行包含两个正整数 $n(1\le n\le 10000)和k(0\le k\le 1000)$第二行包含 $n$个整数，分别表示 $c_i(0\le c_i\le {10}^9)$ OUTPUT 输出一行表示答案 SAMPLE INPUT 3 1 1 1 1 SAMPLE OUTPUT 1 SOLUTION “玲珑杯”ACM比赛 Round #15 Submit  summary  Discuss

解析：暴力遍历1~k+1，选出最优解，注意处理不成立的情况

代码：

#include<bits/stdc++.h> #define N 300009 using namespace std; typedef long long LL; const LL INF = 1LL<<60; int w[N], n, k; LL solve(int s) { LL num = 0ll; int now; for(int j = s; j <= n; j += k*2+1) { num += w[j]; now = j; //if(j + k < n && j + 2*k > n) return -1; } if(now + k < n) return INF; return num; } int main() { LL ans = INF; while(~scanf("%d%d", &n, &k)) { for(int i = 1; i <= n; i++) scanf("%d", &w[i]); for(int i = 1; i <= min(k + 1, n); i++) { LL num = solve(i); if(num < 0) continue; ans = min(ans, num); } cout << ans << endl; } return 0; } //int main() //{ // LL ans = 1LL<<60; // scanf("%d%d", &n, &k); // int now; // for(int i = 1; i <= n; i++) scanf("%d", &w[i]); // for(int i = 1; i <= min(k + 1, n); i++) // { // LL sum = 0; // for(int j = i; j<=n; j+=2*k+1) // { // now = j; // sum += w[j]; // } // if(now + k>=n) // ans = min(ans, sum); // } // cout<<ans<<endl; // return 0; //}