P1220代码求调
  • 板块灌水区
  • 楼主God_Max_Me
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/1/6 15:56
  • 上次更新2023/10/24 05:23:23
查看原帖
P1220代码求调
632128
God_Max_Me楼主2023/1/6 15:56

样例过了,提交后全wa,下载数据1发现居然就跟样例一样的,但是提交了好几次,明明样例对的就是不让过,求调

#include<bits/stdc++.h>
//#define int long long
#define endl "\n"
using namespace std;
int n,c;
int dis[60],w[60];
int dp[60][60][3];//dp[i][j][k]表示关掉i到j的路灯且最后站在i或j的位置(k=0时站在i,k=1时站在j)时的最小功率 
signed main()
{
	ios::sync_with_stdio(0);
	scanf("%d%d",&n,&c);
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;++i)
	{
		cin>>dis[i];
		cin>>w[i];
		w[i]+=w[i-1];//功率前缀和 ,距离因为是给的位置,已经是前缀和了 
	}
	dp[c][c][0]=dp[c][c][1]=0;//人站在中途的起点时dp为0,初始化 
	for(int len=2;len<=n;++len)//枚举长度 
	{
		for(int i=1;i+len-1<=n;++i)//枚举i 
		{
			int j=i+len-1; 
			//一下dp方程中的dis...*w...就是指路灯间的距离(因为速度为1,所以距离就为时间)乘上功率,就是所花的功率 
			dp[i][j][0]=min(dp[i+1][j][0]+(dis[i+1]-dis[i])*(w[i])+(w[n]-w[j])*(dis[i+1]-dis[i]),dp[i+1][j][1]+(dis[j]-dis[i])*(w[n]-w[j])+(w[i])*(dis[j]-dis[i]));
			dp[i][j][1]=min(dp[i][j-1][1]+(dis[j]-dis[j-1])*(w[i-1])+(dis[j]-dis[j-1])*(w[n]-w[j-1]),dp[i][j-1][0]+(dis[j]-dis[i])*(w[n]-w[j-1])+(dis[j]-dis[i])*(w[i-1]));
		}
	}
	cout<<min(dp[1][n][0],dp[1][n][1]);//求最小值 
	return 0;
}
2023/1/6 15:56
加载中...