AC 的:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;
const int N = 3e5 + 5;
int n;
int a[N], b[N];
LL f[N][3];
int main()
{
int tt;
scanf("%d", &tt);
while (tt -- )
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &a[i], &b[i]);
for (int i = 0; i <= n; i ++ ) f[i][0] = f[i][1] = f[i][2] = infLL;
f[0][0] = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= 2; j ++ )
for (int k = 0; k <= 2; k ++ )
if (a[i - 1] + k != a[i] + j) f[i][j] = min(f[i][j], f[i - 1][k] + b[i] * j);
printf("%lld\n", min({f[n][0], f[n][1], f[n][2]}));
}
return 0;
}
写成滚动数组,样例就只会输出 0 了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;
const int N = 3e5 + 5;
int n;
int a[N], b[N];
LL f[2][3];
int main()
{
int tt;
scanf("%d", &tt);
while (tt -- )
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &a[i], &b[i]);
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= 2; j ++ )
for (int k = 0; k <= 2; k ++ )
if (a[i - 1] + k != a[i] + j)
f[i & 1][j] = min(f[i & 1][j], f[i - 1 & 1][k] + b[i] * j);
printf("%lld\n", min({f[n & 1][0], f[n & 1][1], f[n & 1][2]}));
}
return 0;
}