42分MLE求助
查看原帖
42分MLE求助
550596
INORI_for_U楼主2022/3/4 16:21

不知道怎么处理MLE,希望大佬能够帮助

#include<bits/stdc++.h>
using namespace std;

const int N=2e4+9;
int r[N],l[N],dp[N][N];
int n;

int main()
{
	scanf("%d",&n);
	int i,j;
	for(i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
	dp[1][r[1]]=r[1]-1;
	for(i=r[1]-1;i>=1;i--)dp[1][i]=dp[1][i+1]+1;
	for(i=r[1]+1;i<=n;i++)dp[1][i]=dp[1][i-1]+1;
	for(i=2;i<=n;i++)
	{
		int l1=l[i],r1=r[i];
		dp[i][l1]=dp[i-1][r1]+r1-l1+1;
		dp[i][r1]=dp[i-1][l1]+r1-l1+1;
		for(j=l1-1;j>=1;j--)dp[i][j]=dp[i][j+1]+1;
		for(j=r1+1;j<=n;j++)dp[i][j]=dp[i][j-1]+1;
		for(j=l1+1;j<r1;j++)dp[i][j]=min(dp[i][l1]+j-l1,dp[i][r1]+r1-j);
	}
	printf("%d",dp[n][n]);
	return 0;
}
2022/3/4 16:21
加载中...