T1
2. 竞赛真理
题目ID：1306必做题100分
最新提交：
Wrong Answer
50 分
历史最高：
Wrong Answer
50 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
TENSHI在经历了无数次学科竞赛的失败以后，得到了一个真理：做一题就要对一题！但是要完全正确地做对一题是要花很多时间（包括调试时间），而竞赛的时间有限。所以开始做题之前最好先认真审题，估计一下每一题如果要完全正确地做出来所需要的时间，然后选择一些有把握的题目先做。 当然，如果做完了预先选择的题目之后还有时间，但是这些时间又不足以完全解决一道题目，应该把其他的题目用贪心之类的算法随便做做，争取“骗”一点分数。
输入格式：
第一行有两个正整数
�
N和
�
T，表示题目的总数以及竞赛的时限（单位秒）。以下的
�
N行，每行４个正整数
�
1
�
W1
i
、
�
1
�
T1
i
、
�
2
�
W2
i
、
�
2
�
T2
i
，分别表示第
�
i题：完全正确做出来的得分，完全正确做出来所花费的时间（单位秒），“骗”来的分数，“骗”分所花费的时间（单位秒）。
输出格式：
根据每一题解题时间的估计值，确定一种做题方案（即哪些题目认真做，哪些题目“骗”分，哪些不做），使能在限定的时间内获得最高的得分，
样例输入：
4 10800
18 3600 3 1800
22 4000 12 3000
28 6000 0 3000
32 8000 24 6000
样例输出：
50
数据范围：
3
≤
�
≤
30
，
2
≤
�
≤
1080000
，
1
≤
�
1
�
、
�
2
�
≤
30000
，
1
≤
�
1
�
、
�
2
�
≤
�
3≤N≤30，2≤T≤1080000，1≤W1
i
、W2
i
≤30000，1≤T1
i
、T2
i
≤T
时间限制：
1000
空间限制：
65536
代码：
#include <iostream>
#include <vector>
#include <algorithm>
// 定义题目结构体
struct Problem {
int fullScore; // 完全正确做出来的得分
int fullTime; // 完全正确做出来所花费的时间
int cheatScore; // “骗”来的分数3的时间
};
// 比较函数，用于排序，优先考虑完全正确做题的性价比
bool cmp(const Problem& a, const Problem& b) {
double ratioA = static_cast<double>(a.fullScore) / a.fullTime;
double ratioB = static_cast<double>(b.fullScore) / b.fullTime;
return ratioA > ratioB;
}
int main() {
int n, t;
std::cin >> n >> t;
std::vector<Problem> problems(n);
for (int i = 0; i < n; ++i) {
std::cin >> problems[i].fullScore >> problems[i].fullTime >> problems[i].cheatScore >> problems[i].cheatTime;
}
// 先对题目按照完全正确做题的性价比排序
std::sort(problems.begin(), problems.end(), cmp);
int score = 0;
int timeUsed = 0;
for (const Problem& p : problems) {
if (timeUsed + p.fullTime <= t) {
score += p.fullScore;
timeUsed += p.fullTime;
} else if (timeUsed + p.cheatTime <= t) {
score += p.cheatScore;
timeUsed += p.cheatTime;
}
}
std::cout << score << std::endl;
return 0;
}//50分
T2
3. 寿司选择
题目ID：15702必做题100分
最新提交：
Wrong Answer
20 分
历史最高：
Wrong Answer
20 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
此方十分喜爱吃寿司。作为一名重度阿宅，出门吃饭是极其困难的。她在手机上选择了一家寿司店，一共有
�
n种寿司，每个寿司的价格为
�
�
a
i
，且只能点一份，起送价为
�
m元，此方想要知道她最少要花多少钱才能满足起送条件。
输入格式
第一行输入两个整数
�
(
1
≤
�
≤
200
)
n(1≤n≤200)和
�
(
1
≤
�
≤
50000
)
m(1≤m≤50000)。
第二行输入
�
n个整数
�
1
,
�
2
,
.
.
.
,
�
�
(
�
≤
∑
�
�
≤
50000
)
a
1
,a
2
,…,a
n
(m≤∑a
i
≤50000)。
输出格式
输出一个整数，表示满足起送条件的最少花费。
样例
Input 1
3 10
3 7 9
Output 1
10
Input 2
5 12
10 11 7 8 9
Output 2
15
Input 3
3 8
1 6 9
Output 3
9
样例解释
样例1，我们选择价格为
3
3和
7
7的寿司即可满足条件。
样例2，我们选择价格为
7
7和
8
8的寿司，花费了
15
15块，满足条件。
样例3，我们选择价格为
9
9的寿司即可。
数据范围
�
(
1
≤
�
≤
200
)
n(1≤n≤200)，
�
(
1
≤
�
≤
50000
)
m(1≤m≤50000)，
�
�
(
�
≤
∑
�
�
≤
50000
)
a
i
(m≤∑a
i
≤50000)
代码：
#include<bits/stdc++.h>
using namespace std;
int a[50005],dp[50005];
int main(){
int n,m,s=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
s+=a[i];
}
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=s;j>=a[i];j--){
dp[j]=min(dp[j],dp[j-a[i]]+a[i]);
}
}
for(int i=m;i<=s;i++){
if(dp[i]!=0x3f3f3f&&dp[i]>=m){
cout<<dp[i];
break;
}
}
return 0;
}
//20分
T3
4. 抢劫银行
题目ID：7158拓展题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
0 分
时间限制: 1000ms
空间限制: 512000kB
题目描述
一个劫匪要去抢劫n家银行，每家银行有一定的现金，每抢一家银行该劫匪有一定几率被警察抓住，但是当该劫匪连续作案被抓住的几率小于p时他就可以逃脱，问该劫匪在不被捕的情况下最多能抢到多少钱？
输入格式
第一行为用例组数T，每组用例第一行为一个浮点数P和一个整数n分别表示被捕的几率上限以及该劫匪计划抢劫的银行数量，之后n行每行一个整数M和一个浮点数p表示该家银行的现金数以及该劫匪抢劫该家银行被捕的几率。
0<�≤1000<T≤100
0.0≤�≤1.00.0≤P≤1.0
0<�≤1000<n≤100
0≤��≤1000≤Mj≤100
0.0≤��≤1.00.0≤pj≤1.0
输出格式
对于每组用例，输出该劫匪在不被捕的情况最多能抢到多少钱
样例
Input 1
3 0.04 3 1 0.02 2 0.03 3 0.05 0.06 3 2 0.03 2 0.03 3 0.05 0.10 3 1 0.03 2 0.02 3 0.05
Output 1
2 4 6
代码：
#include <bits/stdc++.h>
using namespace std;
int t,m,C[10050];
double g[10005],dp[10005],p;
int main() {
int t,n;
cin>>t;
while(t--) {
memset(dp,0,sizeof(dp));
memset(g,0,sizeof(g));
memset(C,0,sizeof(C));
cin>>p>>n;
int sum =0;
for(int i=1; i<=n; i++) {
cin >>C[i]>>g[i];
g[i]=1.00-g[i];
sum +=C[i];
}
dp[0]=1;
for(int i =1; i<=n; i++) {
for(int j=sum; j>=C[i]; j--) {
dp[j]=max(dp[j],dp[j-C[i]]*g[i]);
}
}
bool f =0;
for(int i =sum; i >=0; i--) {
if(dp[i]>p) {
cout <<i<<endl;
f=1;
break;
}
}
if(f==0) {
cout<<0<<endl;
}
}
return 0;
}
//0分