【8.12测试】卖萌

àì夳堔傛蜴生んèń 2021-10-24 04:54 284阅读 0赞

卖萌

【题目背景】

听说 kscla 小时候，会二分空间，在 MLE 与 RE 之间来回穿梭。但辉夜同学就不会，她只会卖萌，所以她的空间只会越开越大，越开越大。。。

【问题描述】

一次考试有 n 道题，对于第 i 道题，暴力分为 a\[i\]，满分为 b\[i\]，正解所需空间为 l\[i\]，空间限制为 r\[i\]。显然 r\[i\]>=l\[i\]>0，b\[i\]>=a\[i\]>=0。

设这题辉夜开的空间为 f\[i\]，若 f\[i\]>r\[i\],那么这题就会 MLE ,得不到分数。若 l\[i\]<=f\[i\]<=r\[i\]，就能得到 b\[i\] 的满分。若 f\[i\]<l\[i\] ,就只有 a\[i\] 的暴力分（暴力所需空间小得忽略不计）。

辉夜那么萌，自然题题都会正解，但她每一题所开的空间都不会小于上一题。她想知道，自己最多可以得到多少分。

【输入格式】

第 1 行 1 个整数 n，表示有 n 道题。

接下来 n 行，第 i 行 4 个整数 a\[i\]，b\[i\]，l\[i\]，r\[i\] ,含义如题面所述。

【输出格式】

一个整数，表示最大的得分。

【样例输入】

50 100 5 6

60 100 2 4

10 8888 9 10

5 5 2 8

600 800 7 9

【样例输出】

9838

其中一种最优解：

第 1 题 内存 4 ，得 50 分

第 2 题 内存 4 ，得 100 分

第 3 题 内存 9 ，得 8888 分

第 4 题 内存 9 ，得 0 分

第 5 题 内存 9 ，得 800 分

【数据范围】

所有的数据及答案均为不超过 int 范围的非负整数。

Part 1：朴素线性DP

#include<iostream>
 #include<algorithm>
 #include<queue>
 #include<cmath>
 #include<cstring>
 #include<cstdlib>
 #include<cstdio>
 using namespace std;
 const int N=2002;
 int dp[N][N];
 int n,op,ans;
 //dp[i][j]:前i道题,空间为j,最多分数 
 struct node{
 int a,b,l,r;
 //暴力分，满分，正解空间，最大空间 
 }q[N];
 int main(){
 freopen("mlee.in","r",stdin);
 freopen("mlee.out","w",stdout);
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
 scanf("%d %d %d %d",&q[i].a,&q[i].b,&q[i].l,&q[i].r);
 for(int i=1;i<=n;i++){
 //第i道题目 
 
 for(int j=0;j<q[i].l;j++)//第i题用得空间j
 for(int k=0;k<=j;k++)//第i-1题用的空间k
 dp[i][j]=max(dp[i][j],dp[i-1][k]+q[i].a);
 
 for(int j=q[i].l;j<=q[i].r;j++)//第i题用得空间j 
 for(int k=0;k<=j;k++)//第i-1题用的空间k
 dp[i][j]=max(dp[i][j],dp[i-1][k]+q[i].b);
 
 for(int j=q[i].r+1;j<=2000;j++)//第i题用得空间j 
 for(int k=0;k<=j;k++)//第i-1题用的空间k
 dp[i][j]=max(dp[i][j],dp[i-1][k]); 
 } 
 for(int i=0;i<=2000;i++)
 ans=max(ans,dp[n][i]);
 printf("%d",ans);
 return 0;
 }

Part 2： 唔……滚动数组优化，但居然就10分，哭了。

#include<iostream>
 #include<algorithm>
 #include<queue>
 #include<cmath>
 #include<cstring>
 #include<cstdlib>
 #include<cstdio>
 using namespace std;
 const int N=150002;
 int dp[2][N];
 int n,op,ans,cnt=1,biu;
 //dp[i][j]:前i道题,空间为j,最多分数 
 struct node{
 int a,b,l,r;
 //暴力分，满分，正解空间，最大空间 
 }q[N];
 int main(){
 freopen("mle.in","r",stdin);
 freopen("mle.out","w",stdout);
 scanf("%d",&n);
 for(int i=1;i<=n;i++){
 scanf("%d %d %d %d",&q[i].a,&q[i].b,&q[i].l,&q[i].r);
 biu=max(biu,q[i].r);
 }
 
 for(int i=1;i<=n;i++){
 //第i道题目 
 
 for(int j=0;j<q[i].l;j++)//第i题用得空间j
 for(int k=0;k<=j;k++)//第i-1题用的空间k
 dp[cnt][j]=max(dp[cnt][j],dp[cnt^1][k]+q[i].a);
 
 for(int j=q[i].l;j<=q[i].r;j++)//第i题用得空间j 
 for(int k=0;k<=j;k++)//第i-1题用的空间k
 dp[cnt][j]=max(dp[cnt][j],dp[cnt^1][k]+q[i].b);
 
 for(int j=q[i].r+1;j<=biu;j++)//第i题用得空间j 
 for(int k=0;k<=j;k++)//第i-1题用的空间k
 dp[cnt][j]=max(dp[cnt][j],dp[cnt^1][k]);
 
 cnt^=1; 
 } 
 for(int i=0;i<=biu;i++)
 ans=max(ans,dp[cnt^1][i]);
 printf("%d",ans);
 return 0;
 }

Part 3：满分程序：线段树优化DP……jjj正在研究中%%%

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11340776.html