求助!dp只有萌新水平炸成50!
查看原帖
求助!dp只有萌新水平炸成50!
184500
hanzhongtlx楼主2020/4/30 23:12

Rt,WA 5 个点,枯了。
数据:测试点#2

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

#define read(x) scanf("%d",&x)
#define inf 1e9
#define MAXN 55

int n,c;
int xa[MAXN],xb[MAXN];
int dp[MAXN][MAXN][3],sum[MAXN];
int a,b;

int main()
{
	read(n),read(c);
	for(int i=1;i<=n;i++) read(xa[i]),read(xb[i]);
	sum[0]=0;
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+xb[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) dp[i][j][0]=dp[i][j][1]=inf;
	}
	dp[c][c][0]=dp[c][c][1]=0;
	for(int i=c-1;i>=1;i--)
	{
		dp[i][c][0]=dp[i+1][c][0]+(xa[i]-xa[i-1])*(sum[i]+sum[n]-sum[c]);
	}
	for(int i=c+1;i<=n;i++)
	{
		dp[c][i][1]=dp[c][i-1][1]+(xa[i]-xa[i-1])*(sum[n]-sum[i-1]+sum[c-1]);
	}
	for(int l=c-1;l>=1;l--)
	{
		for(int r=c+1;r<=n;r++)
		{
			a=dp[l+1][r][0]+(xa[l+1]-xa[l])*(sum[l]+sum[n]-sum[r]);
			b=dp[l+1][r][1]+(xa[r]-xa[l])*(sum[l]+sum[n]-sum[r]);
			dp[l][r][0]=min(dp[l][r][0],min(a,b));
			a=dp[l][r-1][0]+(xa[r]-xa[l])*(sum[l-1]+sum[n]-sum[r-1]);
			b=dp[l][r-1][1]+(xa[r]-xa[r-1])*(sum[l-1]+sum[n]-sum[r-1]);
			dp[l][r][1]=min(dp[l][r][1],min(a,b));
		}
	}
	printf("%d\n",min(dp[1][n][0],dp[1][n][1]));
	return 0;
} 
2020/4/30 23:12
加载中...