# 拼车记HDU4526

xiaoxiao2021-02-28  26

N <= 100，K <= 100，D <= 100，S <= 100，1 <= Zi <= 4，1<= T(i) <= T(i+1) <= S

Input

2 2 10 5

1 1

2 2

Output

14

N <= 100，K <= 100，D <= 100，S <= 100，1 <= Zi <= 4，1<= T(i) <= T(i+1) <= S

#include<iostream> #include<cstdio> #include<string.h> using namespace std; int r[105][105]; #define MAX 0x3f3f3f3f int n,k,d,s; int a[105],b[105]; int bfs(int ta,int pop) { if(pop<=0) return 0; if(ta>k) return MAX; if(r[ta][pop]!=MAX) return r[ta][pop]; return r[ta][pop]=min(bfs(ta+1,pop),bfs(ta+1,pop-b[ta])+d)+(a[ta]-a[ta-1])*pop; } int main() { cin>>n>>k>>d>>s; int sum=0,flag=0; for(int i=1;i<=k;i++) { cin>>a[i]>>b[i]; } memset(r,MAX,sizeof(r)); int ans=bfs(1,n); if(ans>=MAX) { cout<<"impossible"<<endl; } else { cout<<ans<<endl; } }

#include<iostream> #include<cstdio> using namespace std; #define MAX 0x3f3f3f3f int dp[110][110]; int main() { int n,k,d,s; cin>>n>>k>>d>>s; for(int i=0;i<=k;i++) { for(int j=0;j<=n;j++) { dp[i][j]=MAX; } } dp[0][0]=0; for(int i=1;i<=k;i++) { int ti,num; for(int j=0;j<=n;j++) { dp[i][j]=dp[i-1][j]; } cin>>ti>>num; for(int j=0;j<=n;j++) { for(int k1=0;k1<=num;k1++) { if(k1<=j) { dp[i][j]=min(dp[i][j],dp[i-1][j-k1]+k1*ti+d); } } } } if(dp[k][n]<MAX) cout<<dp[k][n]<<endl; else cout<<"impossible"<<endl; }