蒟蒻好不容易自己想出来了一种dp结果错了!!!求进
查看原帖
蒟蒻好不容易自己想出来了一种dp结果错了!!!求进
225039
Future_Zero楼主2020/7/22 15:30

题解dp全是背包做法 有没有大佬看看我这个dp错在哪里    \ \ \ \ 居然样例过了

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int n,m,d,s;
int f[N][N],sum[N],wait[N][N];
struct car
{
	int t,z;
} a[N];
int main()
{
	cin>>n>>m>>d>>s;
	for(int i=1;i<=m;++i)
		cin>>a[i].t>>a[i].z,
		sum[i]=sum[i-1]+a[i].z;  //sum储存前i个司机的总载人数 
	for(int i=1;i<=m;++i)
		for(int j=i;j<=m;++j)
			wait[i][j]=wait[i][j-1]+a[j].t;  //预处理出i至j号车共需要等待的时间 
											//即乘坐i至j号车共额外支付的时间费 
	memset(f,0x7f,sizeof(f));
	for(int i=1;i<=m;++i)
		f[0][i]=0;      //dp边界值 
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			for(int k=j;k<=m;++k)
			{
				int num=sum[k]-sum[j-1];  //出租出j~k载人总数 
				if(i>=num) f[i][k]=min(f[i][k],f[i-num][j-1]+d*(k-j+1)+num*wait[j][k]);
			}
	int ans=1000;
	for(int i=1;i<=n;++i)
		ans=min(ans,f[n][i]);
	cout<<ans;
}
2020/7/22 15:30
加载中...