PHP jQuery表单,带验证
吃一个第一种汉堡耗时m,吃一个第二种耗时n,给你 t 的时间,在尽量使得时间剩下少的情况下,问最多可以吃多少个汉堡,注意实在尽量是的时间剩下的比较少,意思就是 在能做到刚好把时间花完 是最优情况,以尽量多花时间为先决条件,用背包解决,在尽量耗完时间的情况下 再求 吃的最多,瞬秒
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; 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; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[10000 + 5]; int Time[10000 + 5]; void clear() { memset(dp,0,sizeof(dp)); memset(Time,0,sizeof(Time)); } int main() { int m,n,t; while(cin>>m>>n>>t) { clear(); int a[3] = {0,m,n}; for(int i=1;i<=2;i++) { for(int j=a[i];j<=t;j++) { if(Time[j] < Time[j - a[i]] + a[i]) { Time[j] = Time[j - a[i]] + a[i]; dp[j] = dp[j - a[i]] + 1; } if(Time[j] == Time[j - a[i]] + a[i]) dp[j] = max(dp[j],dp[j - a[i]] + 1); } } if(Time[t] == t) cout<<dp[t]<<endl; else cout<<dp[t]<<" "<<t - Time[t]<<endl; } return EXIT_SUCCESS; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。