求助,无限郁闷ing
感觉方法和解题报告差不多啊,而且时间复杂度也已经是N*K了,怎么还一个劲儿的TLE呢?
#include <algorithm>
using namespace std;
const int INF = (1<<31)-1;
const int MaxN = 20002;

int s[MaxN] = {0};
int f[MaxN][102];

int main()
{
    int T;
    int N, K, L;
    int i, j, k;
    int tmp, ans, num;

    scanf(\"%d\", &T);
    while (T--) {
        scanf(\"%d %d %d\", &N, &K, &L);
        K = min(K, N/L);
        /*
        for (i = 1; i <= N; ++i)
            for (j = 1; j <= K; ++j)
                f[i][j] = INF; //*/
        for (i = 1; i <= N; ++i) {
            scanf(\"%d\", &num);
            s[i] = s[i-1] + num;
            f[i][1] = s[i];
        }
        for (j = 2; j <= K; ++j) {
            tmp = INF;
            for (i = L*j; i <= N; ++i) {
                tmp = min(tmp, f[i-L][j-1]-s[i-L]*j);
                f[i][j] = s[i]*j + tmp;
            }
        }
        /*
        for (i = 1; i <= N; ++i) {
            for (j = 1; j <= K; ++j) {
                printf(\"f[%d][%d]=\" , i, j);
                if (f[i][j]==INF) printf(\"%-3c\", \'#\');
                else printf(\"%-3d\", f[i][j]);
            }
            puts(\"\");
        }// */
        ans = f[N][1];
        for (i = 2; i <= K; ++i)
            ans = min(ans, f[N][i]);
        printf(\"%d\\n\", ans);
    }
    return 0;
}
//*/
以下程序AC:
#include <algorithm>
using namespace std;
const int INF = (1<<31)-1;
const int MaxN = 20002;

int s[MaxN] = {0};
int f[102][MaxN];

int main()
{
int T;
int N, K, L;
int i, j, k;
int tmp, ans, num;

scanf(\"%d\", &T);
while (T--) {
scanf(\"%d %d %d\", &N, &K, &L);
K = min(K, N/L);
/*
for (i = 1; i <= N; ++i)
for (j = 1; j <= K; ++j)
f[j][i] = INF; //*/
for (i = 1; i <= N; ++i) {
scanf(\"%d\", &num);
s[i] = s[i-1] + num;
f[1][i] = s[i];
}
for (j = 2; j <= K; ++j) {
tmp = INF;
for (i = L*j; i <= N; ++i) {
tmp = min(tmp, f[j-1][i-L]-s[i-L]*j);
f[j][i] = s[i]*j + tmp;
}
}
/*
for (i = 1; i <= N; ++i) {
for (j = 1; j <= K; ++j) {
printf(\"f[%d][%d]=\" , i, j);
if (f[j][i]==INF) printf(\"%-3c\", \'#\');
else printf(\"%-3d\", f[j][i]);
}
puts(\"\");
}// */
ans = f[1][N];
for (i = 2; i <= K; ++i)
ans = min(ans, f[i][N]);
printf(\"%d\\n\", ans);
}
return 0;
}
//*/
【chedan的帖子因发AC代码被删除】

你的程序把f的两维交换位置就可以了。
收到,明白原因和机理了,十分感谢~
© 2015 HUST ACMICPC TEAM. All Right Reserved.