Gym - 102392B點
題意：Steve想要在游戲中升到 兩級，給你s1和s2 分別為1級需要的經(jīng)驗和二級需要的經(jīng)驗，然后給你n給任務(wù)，任務(wù)在1級前和在1級后的經(jīng)驗不同，完成的時間也不同，在剛剛升1級時，所溢出的經(jīng)驗加到2級所需的經(jīng)驗中，求升二級所用的最少時間。
思路：dp。dp[i][j],i代表做任務(wù)的總經(jīng)驗，j代表加到1級的經(jīng)驗值，為了能夠讓所有的可能都枚舉到，要先讓任務(wù)進行排序，按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; }

總結(jié)

以上是生活随笔為你收集整理的简单思维dp-- Gym - 102392B的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。