1. House robbery: Given an array of non-negative integers representing the amount stored in each house, calculate the maximum amount you can steal in one night without touching the alarm device.
Input: Each test case has two lines, the first line has only one integer N, which means there are N houses
The second line has N integers, representing the amount in each house, and the amount range is [0, 1000].
Out: The highest amount you can get
In: 4 1 3 2 1 5 2 7 9 3 1 Out: 4 12
#include<iostream>
#include<string>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
int rob(vector<long> & nums) {
int sumOdd = 0;int sumEven = 0;
for (int i = 0; i < nums. size(); i ++ ) {
if (i % 2 == 0) {
sumEven += nums[i];
sumEven = max(sumOdd, sumEven);
} else {
sumOdd + = nums[i];
sumOdd = max(sumOdd, sumEven);
}
}
return max(sumOdd, sumEven);
}
int main() {
long n, sum;
while(scanf("%d", &n)!=EOF) {
vector<long>nums(n); long temp;
for(int i=0; i<n; i ++ ) {
cin>>temp;
nums.push_back(temp);
}
sum=rob(nums);
cout<<sum<<endl;
nums. clear();
}
return 0;
}
2. Multiplication times of matrix chain multiplication: Let A1,?A2,?…,?An be the matrix sequence, Ai is a matrix of order Pi?1?*?Pi?=?1,?2, ?…,?n. Try to determine the order of matrix multiplication so that the total number of multiplications of elements in the process of computing A1A2…An is the least.
Input: an integer n(1≤n≤300) in the first line, indicating that there are n matrices in total. The second line n? + ?1 integer P0,?P1,?…,?Pn (1≤Pi≤100) , the number of rows of the i matrix is Pi?1, and the number of columns is Pi .
Out: output the least number of element multiplications for each group of data.
In: 5 74 16 58 58 88 80 5 10 1 50 50 20 5 Out: 342848 3650
#include<iostream>
#include<string>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX=400; const int MIN=0x3f3f3f3f;
int qq[MAX][MAX]; int n, a[MAX];
int hanshu(int a, int b);
int main() {
while(cin>>n) {
for(int i = 0; i <= n; i ++ ) {
cin>>a[i];
}
memset(qq, -1, sizeof(qq));
int temp=hanshu(0,n);
cout<<temp<<endl;
}
return 0;
}
int hanshu(int aa, int bb){
if(aa == bb - 1){
return 0;
}
int &ans = qq[aa][bb];
if(ans != -1){
return ans;
}
ans = MIN;
for(int i = aa + 1; i < bb; i + + ){
ans=min(ans, hanshu(aa, i) + hanshu(i, bb) + a[aa] * a[i] * a[bb]);
}
return ans;
}
3.Investment problem: m yuan, n investment, fi(x): invest x yuan The benefit of the i-th item. Find the investment plan that maximizes the total benefit.
Input: m n in the first row of each data set, indicating that there are m yuan and n investments in total.
Each of the next n lines contains m integers fi(j) representing the income of the i-th project investment of j yuan,
For all i, fi(0)?=?0.
Output: First output a line, an integer represents the maximum benefit. Then the second line sequentially outputs the investment amount of each project that can get the maximum benefit, separated by spaces. If there are multiple solutions, any one can be output.
Input: 5 4 11 12 13 14 15 0 5 10 15 20 2 10 30 32 40 20 21 22 23 24
Out: 61 1 0 3 1
#include<stdio.h>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <complex>
#include <vector>
#include <algorithm>
const int maxn = 1e3 + 10; typedef long long LL; int m, n;
LL dp[maxn][maxn];
int inc[maxn][maxn], record[maxn][maxn];
void ReverseOutputAns(int i, int j){
if(i == 0) return;
ReverseOutputAns(i - 1, j - record[i][j]);
printf(" %d" + (i == 1), record[i][j]);
}
int main(){
while(scanf("%d%d", & amp;m, & amp;n) != EOF){
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i ++ ){
inc[i][0] = 0;
for(int j = 1; j <= m; j ++ )
scanf("%d", &inc[i][j]);
}
for(int i = 1; i <= n; i ++ ){
for(int j = 0; j <= m; j ++ ){
dp[i][j] = record[i][j] = 0;
for(int k = 0; k <= j; k ++ ){
if(inc[i][k] + dp[i - 1][j - k] > dp[i][j]){
dp[i][j] = inc[i][k] + dp[i - 1][j - k];
record[i][j] = k;
}
}
}
}
printf("%d\\
", dp[n][m]);
ReverseOutputAns(n, m);
printf("\\
");
}
return 0;
}
4. The longest common subsequence: find the longest of the two sequences. Each set of test samples is one line, two sets of strings, each set not exceeding 1000, separated by spaces. Find the longest common subsequence, all lowercase letters.
Input: Each group of test samples is one line, two groups of strings, each group not exceeding 1000, separated by spaces.
Output: For each test instance, output the length of the longest common subsequence, and the output of each instance occupies one line.
In: abcfbc abfcab programming contest abcd mnp Out: 4 2 0
#include<iostream>
#include <cstring>
#include<string>
#include <cmath>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>vec;set<string>k;
int sum; string x,y;
int checklength(int a, int b);
void out(int a, int b, string list);
int main() {
while(cin>>x>>y) {
int x1=x. length(); int x2=y. length();
sum=checklength(x1, x2);
cout<<sum<<endl;
}
return 0;
}
int checklength(int a, int b) {
vec=vector<vector<int>>(a+1,vector<int>(b+1));
for(int i=0; i<a + 1; + + i) {
for(int j=0; j<b + 1; + + j) {
if (i == 0 || j == 0) {
vec[i][j] = 0;
} else if(x[i-1] == y[j-1]) {
vec[i][j] =vec[i-1][j-1] + 1;
} else {
vec[i][j] = max(vec[i-1][j], vec[i][j-1]);
}
}
}
return vec[a][b];
}
void out(int a, int b, string list) {
while (a>0 & amp; & amp; b>0) {
if (x[a-1] == y[b-1]) {
list.push_back(x[a-1]);
--a;--b;
} else {
if (vec[a-1][b] > vec[a][b-1]) {
--a;
} else if (vec[a-1][b] < vec[a][b-1]) {
--b;
} else {
out(a-1, b, list); out(a, b-1, list);
return;
}
}
}
reverse(list.begin(),list.end());
k.insert(list);
}
5. Maximum substring sum: Given an integer array, find a continuous subarray with the maximum sum (the subarray contains at least one element), and return its maximum sum.
Input: There are multiple sets of test data. For each set of test data, the first line has only one integer N, representing the size of the array. The second line has N integers
Output: Only one line is output for each set of test data, including an integer representing the maximum substring sum.
In: 9 -2 1 -3 4 -1 2 1 -5 4 Out: 6
#include<iostream>
#include<string>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
class problem {
public:
int submax(vector<int> & nums) {
int len = nums. size();
vector<int> a(len);
a[0] = nums[0];
int ans = a[0];
for(int i = 1; i < len; i ++ ) {
a[i] = max(a[i-1] + nums[i],nums[i]);
ans = max(ans,a[i]);
}
return ans;
}
};
int main() {
int n,temp,sum;
problem pro;
while(cin>>n) {
vector<int>nums(n);
for(int i=0; i<n; i ++ ) {
cin>>temp;
nums.push_back(temp);
}
sum=pro.submax(nums);
cout<<sum<<endl;
nums. clear();
}
return 0;
}
6. Longest increasing subsequence: Given an array of length N, find the longest increasing subsequence of this array. (Increasing subsequence means that the elements of the subsequence are increasing) For example: 1 3 2 5 4 7 6 9 8, the longest increasing subsequence is 1 3 5 7 9
Input: The input data first includes an integer T (1≤10), indicating the number of test instances.
The first line of each test instance is an integer N(2≤N≤5000), indicating the length of the sequence.
The second line of numbers is a set of arrays, and all integers are in the interval [0,106].
Output: Output the length of the longest increasing subsequence, and the output of each instance occupies one line.
In: 1 9 1 3 2 5 4 7 6 9 8 Out: 5
#include<iostream>
#include<string>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
class problem {
public:
int checklength(vector<int> & nums) {
int com=0;
if (nums. size() <= 1) {
return nums. size();
}
vector<int> list(nums. size() + 1, 1);
for(int i = 1; i < nums. size(); i ++ ) {
for(int j = 0; j < i; j ++ ) {
if(nums[i] > nums[j]) {
list[i] = max(list[j] + 1, list[i]);
}
}
if (list[i] > com) {
com = list[i];
}
}
return com;
}
};
int main() {
int t; int n, temp;
cin >> t; problem pro;
for (int i = 0; i < t; i ++ ) {
cin>>n;
vector<int>nums(n);
for(int i=0;i<n;i ++ ){
cin >> temp;
nums.push_back(temp);
}
int sum = pro. checklength(nums);
cout << sum-1 << endl;
nums. clear();
}
return 0;
}
7.01 Meal card: If the remaining amount on the card is greater than or equal to 5 yuan before purchasing a product, the purchase will be successful (even if the balance on the card is negative after purchase), otherwise it cannot be purchased (even if the amount is sufficient). So everyone wants to keep the balance on the card as low as possible. On a certain day, there are n kinds of dishes for sale in the cafeteria, and each dish can be purchased once. Knowing the price of each dish and the balance on the card, ask how much the minimum balance on the card can be.
Input: multiple sets of data. For each set of data: The first row is a positive integer n, representing the number of dishes. n<=1000. The second line includes n positive integers, representing the price of each dish. The price does not exceed 50. The third line includes a positive integer m, representing the balance on the card. m<=1000. n=0 indicates the end of data.
Output: For each set of inputs, output a line containing an integer representing the smallest possible balance on the card.
In: 1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0 Out: -45 32
#include<iostream>
#include<string>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
int n,sum;int a[2000];int b[2000];
while (scanf("%d", &n)!=EOF) {
if(n==0){//no output request
break;
}
memset(b, 0, sizeof(b));
for (int i = 1; i <= n; i ++ ) {
cin >> b[i];
}
sort(b + 1, b + 1 + n);
int com_sum = b[n];
cin >> sum;
memset(a, 0, sizeof(a));//initialize 0
if (sum < 5) {//before input
cout << sum << endl;
continue;
}
sum = sum - 5;
for (int i = 1; i <= n-1 ; i ++ ) {
for (int j = sum; j >= b[i]; j--) {
int op=a[j - b[i]] + b[i];
a[j] = max(a[j], op);
}
}
int temp=sum + 5 - a[sum] - com_sum;
cout << temp << endl;
}
}