简单思维dp-- Gym - 102392B

Gym - 102392B点
题意：Steve想要在游戏中升到 两级，给你s1和s2 分别为1级需要的经验和二级需要的经验，然后给你n给任务，任务在1级前和在1级后的经验不同，完成的时间也不同，在刚刚升1级时，所溢出的经验加到2级所需的经验中，求升二级所用的最少时间。
思路：dp。dp[i][j],i代表做任务的总经验，j代表加到1级的经验值，为了能够让所有的可能都枚举到，要先让任务进行排序，按x的从小到大。

代码

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define INF 0x3f3f3f3f3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); using namespace std; typedef long long ll; typedef unsigned long long ull; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=10001; const ll N =1500; ll dp[N][N]; struct p {int x,t,y,r;bool operator <(const p &M)const{return x<M.x;} }a[N]; int n,s1,s2; int32_t main() { #ifdef localfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout); #endif // localiosFILL(dp,0x3f);cin>>n>>s1>>s2;int mx=0;for(int i=1;i<=n;i++) {cin>>a[i].x>>a[i].t>>a[i].y>>a[i].r;mx=max(mx,a[i].x);}sort(a+1,a+n+1);int lim1=s1+s2;int lim2=s1+mx;int j1,j2;dp[0][0]=0;for(int i=1;i<=n;i++){for(int j=lim1;j>=0;j--){for(int k=lim2;k>=0;k--){if(dp[j][k]!=INF){j1=min(lim1,a[i].x+j);j2=min(lim1,j+a[i].y);if(k<s1&&k+a[i].x<N){dp[j1][k+a[i].x]=min(dp[j1][k+a[i].x],dp[j][k]+a[i].t);}dp[j2][k]=min(dp[j2][k],dp[j][k]+a[i].r);}}}}ll any=INF;for(int k=s1;k<lim2;k++){any=min(any,dp[lim1][k]);}if(any==INF) cout<<-1;elsecout<<any;return 0; }

总结

以上是生活随笔为你收集整理的简单思维dp-- Gym - 102392B的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。