为啥滚动数组错了。
查看原帖
为啥滚动数组错了。
482728
Engulf楼主2023/1/14 19:19

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;
}
2023/1/14 19:19
加载中...