小易参加了一次考试,这场包含 n 个题目,第 i 个题目的分数是 si 。
如果小易第 i 题目回答正确,他将得到 Si 分,否则该题目他将得到 0 分。
最终的考试得分是所有题目得分的总和。
由于阅卷老师很讨厌数字 5,在阅卷时如果一个学生的考试总分中含有数字 5,那么阅卷老师将气愤地给他 0 分。
那么小易考试的最高得分是多少?
小易参加了一次考试,这场包含 n 个题目,第 i 个题目的分数是 si 。
如果小易第 i 题目回答正确,他将得到 Si 分,否则该题目他将得到 0 分。
最终的考试得分是所有题目得分的总和。
由于阅卷老师很讨厌数字 5,在阅卷时如果一个学生的考试总分中含有数字 5,那么阅卷老师将气愤地给他 0 分。
那么小易考试的最高得分是多少?
输入的第一行是正整数 n(1<=n<=100) ,代表这场考试的题目数。接下一行含有n个正整数 s1,s2,s3....sn (1<= si <=200)
输出一个整数,代表小易考试的最高得分。
5 5 15 5 15 5
40
如果所有题目都答对,总分为45,但里面包含了数字5,所以最高得分应该为40
5 5 15 5 15 8
48
1 5
0
package niuke.wangyi_2021; import java.util.Scanner; public class Main_2 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] res = new int[n]; for(int i = 0 ; i < n ; i++) { res[i] = scanner.nextInt(); } new Main_2().search(res); } private void search(int[] res ) { int max1 = 0; for(int i = 0 ; i < res.length ; i++) { max1 += res[i]; } if(pan(max1)) { System.out.println(max1); return; } boolean[] result = new boolean[max1 + 1]; result[0] = true; for(int i = 0 ; i < res.length ; i++ ) { for(int j = max1 ; j >= res[i] ; j--) { if(result[j]) continue; if(result[j - res[i]]){ result[j] = true; } } } for(int i = max1 ; i >= 0; i--) { if(result[i] && pan(i)) { System.out.print(i); return; } } } private boolean pan(int n) { if(String.valueOf(n).contains("5")) return false; return true; } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] strArr = br.readLine().split(" "); int[] scores = new int[n]; int sum = 0; for(int i = 0; i < n; i++){ scores[i] = Integer.parseInt(strArr[i]); sum += scores[i]; } int[] dp = new int[20001]; // 1~100个1~200的数总和最大为20000 // 求解背包问题 dp[0] = 1; dp[sum] = 1; for(int i = 0; i < n; i++){ dp[scores[i]] = 1; for(int j = 0; j <= sum; j++){ if(dp[j] == 1 && j - scores[i] >= 0) dp[j - scores[i]] = 1; } } // 降序依次检测分数是否符合不含5 for(int score = sum; score >= 0; score--){ if(dp[score] == 1 && !String.valueOf(score).contains("5")){ System.out.println(score); break; } } } }
首先考虑这个问题
我有n个礼物,价值分别为到,我可以选其中0个或者多个,并把它们的价值相加,得到sum,我想知道sum有多少种可能的取值?比如[1,1,1]三个礼物,sum有0,1,2,3四种取值。
dp[i]=1是存在可能的选择方法,使得总和为i。
怎么理解呢?
dp[0]代表空集合,每次取一个score,加入所有集合中,更新!
为了不让同一个礼物反复更新,从后往前,比如[3, .....]这个礼物列表,如果从前往后,j=3时dp[3]=1,j=6时候发现dp[3]是1,那dp[6]也是1,相当于3+3,3用了2次,哒咩!
时间复杂度
复杂度海⭐️
vector<int> possibleSums(const vector<int>& score) { int sum = 0; for (auto n : score) sum += n; vector<int> dp(sum + 1); dp[0] = 1; for (int sco : score) { for (int j = sum; j >= sco; --j) { if (dp[j - sco]) { dp[j] = 1; } } } return dp; }
具体到这一题就是算出所有的取值,然后从后往前检查是否包含5,输出第一个不包含5的分数!
完整代码
#include<bits/stdc++.h> using namespace std; int maxScore(const vector<int>& score) { int sum = 0; for (auto n : score) sum += n; vector<int> dp(sum + 1); dp[0] = 1; for (int sco : score) { for (int j = sum; j >= sco; --j) { if (dp[j - sco]) { dp[j] = 1; } } } auto have5 = [](int n) { while (n) { int m = n % 10; n /= 10; if (m == 5) return true; } return false; }; for (int i = sum; i >= 0; --i) { if (dp[i] && !have5(i)) return i; } return -1; } int main() { int n; cin >> n; vector<int> score(n); for (int i = 0; i < n; i++) cin >> score[i]; cout << maxScore(score); }
//C++背包 如果一开始发现和没有5,直接返回即可 #include <vector> #include <iostream> using namespace std; bool havefive(int sum) { while(sum) { if(sum%10==5) return true; sum/=10; } return false; } int main() { int n; cin>>n; vector<int> v(n); int sum=0; for(int i=0;i<n;i++) { cin>>v[i]; sum+=v[i]; } if(!havefive(sum)) { cout<<sum<<endl; return 0; } vector<bool> dp(sum+1); dp[0]=true; int maxadd=0; for(auto e:v) { maxadd+=e; for(int i=maxadd;i>=e;i--) { if(dp[i-e]==true) dp[i]=true; } } for(int i=sum;i>=0;i--) { if(dp[i]==true&&(!havefive(i))) { cout<<i<<endl; break; } } return 0; }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); ArrayList<Integer> scores = new ArrayList<>(); String[] s = br.readLine().split(" "); for(int i=0;i<n;i++){ scores.add(Integer.parseInt(s[i])); } // 将所有题目分数从大到小排列 scores.sort(Collections.reverseOrder()); // 先对所有分数求和 int sum = scores.stream().mapToInt(Integer::intValue).sum(); // 如果天然的总分有数字5存在 if(String.valueOf(sum).contains("5") && scores != null){ int tempSum = -1; // 逐一尝试总分减去一题分数是不是就不含5了,如果是记录临时总分 // 因为题目分数从大到小排列 经过一轮遍历,可以找到让现在的总分不含5的最大情况 for(int i: scores){ if(!String.valueOf(sum - i).contains("5")){ tempSum = Math.max(tempSum, sum - i); } } // 如果确实可以靠减掉一题分数符合题目要求,说明找到了直接输出结束程序 if(tempSum != -1){ System.out.println(tempSum); return; }else { // 如果没有找到减掉一题符合要求的结果,就减掉分值最低的一题 sum -= scores.get(scores.size() - 1); scores.remove(scores.size() - 1); } } System.out.println(sum); } }
#include <iostream> #include <algorithm> using namespace std; int n,*arr; int result; int now; bool IfNo5(){ string str=to_string(now); int len=str.length(); for(int i=0;i<len;++i) if(str[i]=='5') return 0; return 1; } void dfs(int index){ if(result) return; if(IfNo5()){ result=now; return; } if(index){ if(!result) dfs(index-1); if(!result){ now-=arr[index]; dfs(index-1); now+=arr[index]; } } else{ now-=arr[index]; if(IfNo5()) result=now; now+=arr[index]; } } int main(){ cin>>n; arr=new int[n]; for(int i=0;i<n;++i){ cin>>arr[i]; now+=arr[i]; } if(!IfNo5()){ sort(arr,arr+n); dfs(n-1); } else result=now; cout<<result<<endl; delete[]arr; return 0; }
import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); String[] secLine = br.readLine().trim().split(" "); int[] pts = new int[n]; int sum = 0; for(int i = 0; i < n; i++){ pts[i] = Integer.parseInt(secLine[i]); sum += pts[i]; } Arrays.sort(pts); // 创建一个divide用于检测有没有5 if(!has5(sum)){ System.out.print(sum); }else{ for(int i = 0; i < n; i++) { if(!has5(sum - pts[i])){ System.out.print(sum - pts[i]); break; } } } } private static boolean has5(int num){ boolean has = false; int divide = num; while(divide != 0){ int single = divide % 10; if(single == 5){ has = true; break; } divide /= 10; } return has; } }
n=int(input().strip()) A=list(map(int,input().strip().split())) A=sorted(A) #升序排序 SsumA='%d' % sum(A) while SsumA.count('5')!=0: #和值有5,处理 flag=0 for i in range (len(A)): tmp=A[i] sumA=sum(A)-tmp SsumA='%d' % sumA if SsumA[-1]!='5': del A[i] flag=1 break if flag==0: del A[i] SsumA='%d' % sum(A) print(sum(A))