题解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;
}