营销网站建设网站开发,资讯类网站模板asp,免费校园网站建设,全屏类网站Gym - 102392B点 题意#xff1a;Steve想要在游戏中升到 两级#xff0c;给你s1和s2 分别为1级需要的经验和二级需要的经验#xff0c;然后给你n给任务#xff0c;任务在1级前和在1级后的经验不同#xff0c;完成的时间也不同#xff0c;在刚刚升1级时#xff0c;所溢出…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 mod10001;
const ll N 1500;
ll dp[N][N];
struct p
{int x,t,y,r;bool operator (const p M)const{return xM.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);cinns1s2;int mx0;for(int i1;in;i) {cina[i].xa[i].ta[i].ya[i].r;mxmax(mx,a[i].x);}sort(a1,an1);int lim1s1s2;int lim2s1mx;int j1,j2;dp[0][0]0;for(int i1;in;i){for(int jlim1;j0;j--){for(int klim2;k0;k--){if(dp[j][k]!INF){j1min(lim1,a[i].xj);j2min(lim1,ja[i].y);if(ks1ka[i].xN){dp[j1][ka[i].x]min(dp[j1][ka[i].x],dp[j][k]a[i].t);}dp[j2][k]min(dp[j2][k],dp[j][k]a[i].r);}}}}ll anyINF;for(int ks1;klim2;k){anymin(any,dp[lim1][k]);}if(anyINF) cout-1;elsecoutany;return 0;
}
