1、题目名称：投篮
小明投篮，罚球线投球可得一分，在三分线内投篮得分可以得到 2 分，在三分线以外的地方投篮得分可以得到 3 分，连续投 进得分累计，一旦有一个球没投进则得分清零，重新计算。现给出所有得分记录（清零不计入得分），请你计算一下小明 最多连续投进多少个球？
这个题明显是考最长连续上升子序列，dp状态转移方程即可
dp[i]表示从下标为0到下标为i的最长连续上升子序列
状态转移方程：dp[i]=dp[i-1]+1
只要后面的数比前面的数大就更新加1
最后输出dp数组中最大的数为答案
#include<iostream> using namespace std; int a[10005],dp[10005]; int n,maxx; int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; dp[i]=1;//初始都为1，因为每个数自己都是唯一的上升子序列 } for(int i=1;i<n;i++){ if(a[i]>a[i-1]){//状态转移条件 dp[i]=dp[i-1]+1;//状态转移方程 } } for(int i=0;i<n;i++){ maxx=max(maxx,dp[i]); } cout<<maxx<<endl; return 0; }
2、题目名称：买苹果
小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供 6 个每袋和 8 个每袋的包装 ( 包装不可拆分 ) 。 可是小易现在 只想购买恰好n 个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好 n 个苹果，小易将不会购买。
输入描述：输入1个整数n，表示小易想购买n（1<=n<=100）个苹果
输出描述：输出一个整数表示最少需要购买的袋数，如果不能恰好购买n个苹果则输出-1
输入例子：20
输出例子：3
这个题给我的印象是之前做过的类似的题货币系统和换零钱，这两个题是计算总的方法数，用的是dp动态规划，此题是输出最小的袋数，dp博主没立马想到咋做，但是dfs有思路，就用的dfs做的，望各位读者理解。
#include<iostream> using namespace std; int n,minx=0x3f3f3f; int a[]={6,8};//要么6个一袋要么8个一袋 int flag;//监视哨，作用就是看看是否能凑齐n个苹果 void dfs(int temp,int dep){//tmp表示此时苹果数，dep表示购买的袋数 if(dep>minx){//如果dep超过了最小袋数，就没必要向下继续搜索了 return; } if(temp==n&&dep<minx){//条件成立时，更新最小值，顺便告诉监视哨flag找到能凑齐n个的袋数 minx=dep; flag=1; return; } for(int i=0;i<2;i++){//常规搜索 if(temp+a[i]<=n){ dfs(temp+a[i],dep+1); } } } int main(){ cin>>n; dfs(0,0); if(flag==1){//flag==1说明找到了能凑齐n个苹果的方法数 cout<<minx<<endl; }else{ cout<<-1<<endl; } return 0; }
3、题目名称：打家劫舍
一个小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通 的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数 数组，计算不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
输入例子：1 2 3 1
输出例子：4
这个题看着第一眼就是贪心，博主把贪心的思想应用在了dfs上了，主要加上了 两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警这个条件，注意好本身和旁边的房子是否被标记过就行，代码上附有注释
#include<iostream> using namespace std; int n,maxx; int a[1005];//原数组 int vis[1005];//标记数组 void dfs(int dep,int sum){//dep表示当前搜索的个数，sum表示所能带走的价值 if(dep>=n){//如果dep搜索超出了n个了，就没必要继续搜索了 return; } if(sum>maxx&&dep<n){//更新条件成立 maxx=sum; } for(int i=dep;i<n;i++){对当前位置为起点向后搜索 if(vis[i]==0&&vis[i-1]==0&&vis[i+1]==0){//如果当前位置及前一个位置及后一个位置没有被标记过 vis[i]=1;//只需标记当前位置就行 dfs(dep+1,sum+a[i]);//继续向下搜索 vis[i]=0;//回溯解除标记 } } } int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } if(n==1){//需要分情况讨论，只过了90%样例可能没有考虑这一点 cout<<a[0]<<endl; }else{ dfs(0,0); cout<<maxx<<endl; } return 0; }
4、题目名称：天然气订单
天然气运输成本昂贵，危险性高，为了节省运输成本，提倡绿色环保，需要尽可能的优化订单配送，比如相同地区的天然 气订单可以一次性配送。 现需要向多个地区运输天然气。但是同一个地区可能有多个订单需求。当前仅只知道某些成对的 订单是同一个地区的，同一个地区的天然气需要尽可能一次性配送从而降低运输成本，所以需要尽可能的将同一个地区的 订单放在一起。订单的编号是1 到 n 。
这道题没啥可说的，思路很清晰，按照自己的思路向下顺着写就行，看代码吧。
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int n, m, cnt = 0; vector<int> G[10010]; bool vis[10010] = {false}; void bfs(int u, vector<int>& v) { queue<int> q; q.push(u); v.push_back(u); vis[u] = true; while (!q.empty()) { int x = q.front(); q.pop(); for (int i = 0; i < G[x].size(); ++i) { int y = G[x][i]; if (!vis[y]) { q.push(y); vis[y] = true; v.push_back(y); } } } } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } vector<vector<int>> ans; for (int i = 1; i <= n; ++i) { if (!vis[i]) { vector<int> v; bfs(i, v); ans.push_back(v); ++cnt; } } cout << cnt << endl; sort(ans.begin(), ans.end(), [](vector<int> a, vector<int> b) { return a[0] < b[0]; }); for (auto& v : ans) { sort(v.begin(), v.end()); for (int i = 0; i < v.size(); ++i) { cout << v[i]; if (i < v.size() - 1) { cout << " "; } } cout << endl; } return 0; }
博主本人大一在读，水平有限，文章可能有错误、描述错误的地方，博主的解法不一定为最优解法，望各位大佬指出，共同学习进步。
