首页 > 代码库 > 玲珑杯 Round15 A Reverse the light

玲珑杯 Round15 A Reverse the light

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

官方题解:

对于每一次的操作,显然其周围的2k个灯不会有状态翻转,否则这次就是无效的,于是转换为简单的动态规划问题.
令dp(i)表示将前i+k个灯全部点亮的最小花费,直接转移即可.
复杂度为O(n)。

恩,然后就是dp一下。然而看了题解之后WA了n次,原因何在?

  for(int i = n - k; i <= n; i++)  ans = min(ans, dp[i]);

实际上不能这样, n < k的时候就会出错而不一定是RE。。。。

代码:

 1 #define maxn 10010
 2 int n, k;
 3 long long dp[maxn], c[maxn];
 4 
 5 int main() {
 6     scanf("%d %d", &n, &k);
 7     for(int i = 1; i <= n; i++)
 8         scanf("%lld", &c[i]);
 9     for(int i = 0; i <= n; i++)
10         dp[i] = inf;
11     long long ans = inf;
12     for(int i = 1; i <= 1 + k; i++){
13         if(i > n) break;
14         dp[i] = c[i];
15         if(i + k >= n) ans = min(ans, dp[i]);
16     }
17     for(int i = 2 * k + 2; i <= n; i++){
18         dp[i] = min(dp[i], dp[i - k - k - 1] + c[i]);
19         if(i + k >= n) 
20             ans = min(ans, dp[i]);
21     }
22     cout << ans << endl;
23 }

题目:

1121 - Reverse the lights

Time Limit:2s Memory Limit:256MByte

Submissions:293Solved:86

DESCRIPTION

nn个灯,初始时都是不亮的状态,每次你可以选择一个某一个灯,不妨记为xx,所有满足和xx距离不超过kk的灯的状态都将被翻转,选择第ii个灯的代价记为cici,问最终所有灯都是亮的状态的最小花费.

INPUT
输入有两行,第一行包含两个正整数n(1n10000)k(0k1000)n(1≤n≤10000)和k(0≤k≤1000) 第二行包含nn个整数,分别表示ci(0ci109)ci(0≤ci≤109)
OUTPUT
输出一行表示答案
SAMPLE INPUT
3 1 1 1 1
SAMPLE OUTPUT
1

玲珑杯 Round15 A Reverse the light