萌新O(nv)算法求调，过不了样例

基础思路

状态设置
- $F_{k,i}$ 表示公差为 $k$ 前 $i$ 个电塔的等差数列数。
- 两个 $F$ 一个公差为 $k$ ，一个为 $-k$ 。
状态转移
- 对于 $F_{k, i}$ ，从所有在 $i$ 之前的的与第 $i$ 个电塔差为 $j$ 的 $F$ 方案加一转移而来。

CPP

    	for (int k = 0; k <= D; k++)
    	{
    		for (int i = 1; i <= n; i++)
    		{
    			for (int j = 1; j < i; j++)
    			{
    				if (h[i] - h[j] == k)
    				{
    					dp1[k][i] += dp1[k][j] + 1;
    					dp1[k][i] = dp1[k][i] mod;
    				}
    				if (h[i] - h[j] == -k)
    				{
    					dp2[k][i] += dp2[k][j] + 1;
    					dp2[k][i] = dp2[k][i] mod;
    				}
    			}
    			if(k != 0)
    				ans += dp1[k][i] + dp2[k][i], ans = ans mod;
    			else
    				ans += dp1[k][i], ans = ans mod;
    		}
    	}

然而只有65pts，毕竟接近

\operatorname {O}(n^3)

的复杂度。

然后就在这个代码基础上用那个

O(nv)

的思路修改了，但是连样例都过不了。求调orz

CPP

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

#define mod %998244353

using namespace std;

const int N = 1e3 + 10;
const int M = 1e4 + 10;

int n;
int h[N];
int dp1[M][N];//计算公差为+k 
int dp2[M][N];//计算公差为-k 
int G1[M];
int G2[M];
int ans = 0;
int D = 0, minH = 0x7fffffff, maxH = 0;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> h[i];
		minH = min(minH, h[i]);
		maxH = max(maxH, h[i]);
	}
	
	D = maxH - minH;
	
	for (int k = 0; k <= D; k++)
	{
		memset(G1, 0, sizeof(G1));
		memset(G2, 0, sizeof(G2));
		for (int i = 1; i <= n; i++)
		{
			if (h[i] - k >= 0)
				dp1[k][i] = G1[h[i] - k], G1[h[i]] += dp1[k][i] + 1;
			if (h[i] + k <= maxH && k)
				dp2[k][i] = G2[h[i] + k], G2[h[i]] += dp2[k][i] + 1;
			ans += dp1[k][i] + dp2[k][i];
		}
	}
	
	cout << ans + n;
	return 0;
}

萌新O(nv)算法求调，过不了样例

讨论操作

基础思路

回复

相关推荐

萌新O(nv)算法求调，过不了样例