dp..dp(i, j)表示画两个点为i-j, i的最优答案. dp(i, j) = min{ dp(i-j, k) } + cost[i] (1≤k≤M-j)
令f(i, j) = min{dp(i, j)}, 那么转移时间下降为O(1).然后滚动数组..这道题卡空间..时间复杂度O(NM)
--------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 10001;
const int maxm = 101;
const int INF = 0x3F3F3F3F;
int dp[maxm], f[maxn][maxm], cost[maxn], N, M;
int main() {
memset(f, INF, sizeof f);
scanf("%d%d", &N, &M);
for(int i = 1; i <= N; i++) scanf("%d", cost + i);
int ans = INF;
for(int i = 1; i <= N; i++) {
if(i < M) f[i][0] = dp[0] = cost[i];
for(int j = 1; j <= M; j++) {
if(j > 1) f[i][j] = f[i][j - 1];
if(j > i) continue;
dp[j] = f[i - j][M - j];
if(i <= M) dp[j] = min(dp[j], f[i - j][0]);
f[i][j] = min(f[i][j], dp[j] += cost[i]);
if(N - i + j + 1 <= M) ans = min(ans, dp[j]);
}
}
printf("%d
", ans);
return 0;
}
--------------------------------------------------------------------------------
183. Painting the balls
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
memory limit per test: 4096 KB
input: standard input
output: standard output
output: standard output
Petya puts the N white balls in a line and now he wants to paint some of them in black, so that at least two black balls could be found among any M successive balls. Petya knows that he needs Ci milliliters of dye exactly to paint the i-th ball. Your task is to find out for Petya the minimum amount of dye he will need to paint the balls.
Input
The first line contains two integer numbers N and M (2<=N<=10000, 2<=M<=100, M<=N). The second line contains N integer numbers C1, C2, ..., CN (1<=Ci<=10000).
Output
Output only one integer number - the minimum amount of dye Petya will need (in milliliters).
Sample test(s)
Input
6 3
1 5 6 2 1 3
1 5 6 2 1 3
Output
9
Note
Example note: 1, 2, 4, 5 balls must be painted.