1、题目名称：投篮
小明投篮，罚球线投球可得一分，在三分线内投篮得分可以得到 2 分，在三分线以外的地方投篮得分可以得到 3 分，连续投 进得分累计，一旦有一个球没投进则得分清零，重新计算。现给出所有得分记录（清零不计入得分），请你计算一下小明 最多连续投进多少个球？
这个题明显是考最长连续上升子序列，dp状态转移方程即可
dp[i]表示从下标为0到下标为i的最长连续上升子序列
状态转移方程：dp[i]=dp[i-1] 1
只要后面的数比前面的数大就更新加1
最后输出dp数组中最大的数为答案
代码语言：javascript复制#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做的，望各位读者理解。
代码语言：javascript复制#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上了，主要加上了 两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警这个条件，注意好本身和旁边的房子是否被标记过就行，代码上附有注释
代码语言：javascript复制#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 。
这道题没啥可说的，思路很清晰，按照自己的思路向下顺着写就行，看代码吧。
代码语言：javascript复制#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;
}博主本人大一在读，水平有限，文章可能有错误、描述错误的地方，博主的解法不一定为最优解法，望各位大佬指出，共同学习进步。
