题意:有m辆车,每次最多运n辆过河,过河过去需要t时间回来需要t时间,m辆车一开始并不是都在岸边的,给出m辆车抵达岸边的时间(只有车抵达河岸才能过河),问使得所有车辆过河所需要的最少次数 跟 最早时间
分析:
一开始看题目可能觉得有两个最优解,最少次数跟最早时间,次数最少猜测一下,m%n==0则刚好为m/n次 否则 为m/n+1次,然后考虑最早时间,时间要最早 其实就是最后一辆车最早过河了即可,那么最后一辆车尽早被送走就好,看样子可以贪心
举了几个案例试了一下,若m%n==0则不用说了,每次运n辆车过河即可,这样既保证了次数最少又保证了时间最早
若m%n!=0,那么第一次运m%n辆车,剩下的每次运n辆车即可,所以贪心是可以的
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #include<cctype> #include<queue> #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int> P; //vector<pair<int,int>> ::iterator iter; // //map<ll,int>mp; //map<ll,int>::iterator p; int n,t,m; int time[1000000]; void clear() { memset(time,0,sizeof(time)); } int main() { int Case; scanf("%d",&Case); while(Case--) { scanf("%d %d %d",&n,&t,&m); clear(); int r = m%n; int k = m/n; int ans1 = 0,ans2; if(r) ans2 = k + 1; else ans2 = k; for(int i=1;i<=m;i++) scanf("%d",&time[i]); if(r) ans1 = time[r] + t * 2; int j = 1; while(j <= k) { if(ans1 >= time[j * n + r]) { ans1 += t * 2; if(j == k) ans1 -= t; } else { ans1 = time[j * n + r] + t * 2; if(j == k) ans1 -= t; } j++; } printf("%d %d\n",ans1,ans2); } return 0; }
dp[i]表示送走第i辆车的最早时间
num[i]表示送走第i辆车的次数
注意时间的早和晚不能直接取的,因为车子到了你才能运过河,
所以状态转移方程有个去当前dp数组值与当前的time数组值最大值的地方要注意
dp[i] = min(max(dp[j] + t,time[i]) + t),其中j为 i-n 到i
次数转移就简单了直接 num[i] = num[j] + 1,其中j为最小的
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #include<cctype> #include<queue> #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int> P; //vector<pair<int,int>> ::iterator iter; // //map<ll,int>mp; //map<ll,int>::iterator p; int n,t,m; int time[10000]; int dp[10000]; int num[10000]; void clear() { memset(time,0,sizeof(time)); memset(dp,0,sizeof(dp)); memset(num,0,sizeof(num)); } int main() { int Case = 0; scanf("%d",&Case); while(Case--) { clear(); scanf("%d %d %d",&n,&t,&m); for(int i=1;i<=m;i++) scanf("%d",&time[i]); dp[0] = -t; dp[1] = time[1] + t; num[1] = 1; for(int i=2;i<=m;i++) { for(int j=max(0,i-n);j<i;j++) { int tmp = max(dp[j] + t,time[i]) + t; if(dp[i] == 0) { dp[i] = tmp; num[i] = num[j] + 1; continue; } if(dp[i] > tmp) { dp[i] = tmp; num[i] = num[j] + 1; } } } printf("%d %d\n",dp[m],num[m]); } return 0; }
POJ2336 Ferry Loading II 贪心动规,布布扣,bubuko.com
原文:http://blog.csdn.net/yitiaodacaidog/article/details/25246847