阅读量:0
原题链接：E - Maximum Glutton
题意：你的面前有n盘菜，每盘菜有一个甜度和咸度，如果你吃的菜的总甜度超过限度X或者总咸度超过限度Y，那么你就不可以继续吃了，你最多可以吃几盘菜？
思路：本题有个很直接的思路，那就是动态规划，最直接想到的dp数组是dp[i][j][k]，i代表前i盘菜，j代表吃了菜的总甜度，k代表吃了菜的总咸度，dp[i][j][k]的值是能吃的数量。但是很明显如果这样dp，时间复杂度是O(NXY),明显会超时，而且空间也不支持开80*10000*10000的数组。那么不妨将上述的四种含义换个位置，i代表前i盘菜，j代表吃的菜，k代表吃了的总甜度，dp[i][j][k]的值代表吃了菜的总咸度，这样dp数组最多也就是80*80*10000的大小了，满足了空间复杂度。但是可以满足时间复杂度并且正确的找到答案吗？明显也是可以的，时间复杂度是O(NNX)，符合题目要求，当dp数组被递推完全之后，取遍历前n个，取i盘菜，甜度为k的数组，如果dp数组值满足咸度的要求，那么就i就是我们能够在不超过甜度和咸度的情况下吃的最多的菜，但是根据题意，可以再吃一盘，这个一盘要和n取最小值。
//冷静，冷静，冷静 //调不出来就重构 #pragma GCC optimize(2) #pragma GCC optimize("O3") #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pii; const int N=1e6+10,mod=1000000007; ll f[90][90][10010],n,m,p[N],q[N]; int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); ll xz1,xz2; cin>>n>>xz1>>xz2; for(int i=0;i<=85;i++) { for(int j=0;j<=85;j++) { for(int k=0;k<=10005;k++) { f[i][j][k]=1e18; } } } for(int i=1;i<=n;i++)cin>>p[i]>>q[i]; f[0][0][0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=i;j++) { for(int k=0;k<=xz1;k++) { if(i-1>=j)f[i][j][k]=min(f[i-1][j][k],f[i][j][k]);//如果不选就从i-1个里面选j个，和从i里面选j个转移 if(k-p[i]>=0)f[i][j][k]=min(f[i][j][k],f[i-1][j-1][k-p[i]]+q[i]); //从甜度为k-p[i]转移 } } } for(ll i=n;i;i--) { for(int j=0;j<=xz1;j++) { if(f[n][i][j]<=xz2) { cout<<min(i+1,n); return 0; } } } cout<<1;//如果一盘菜都不能吃，吃了就超限，那么就只能吃一盘 return 0; } 