本周学习总结22.5.30-6.5：贪心、动态规划DP

[USACO07DEC]Bookshelf B - 洛谷这个题的题意是在一串数中取最少的数，并且使取的数和大于等于给定数，是一个贪心入门题，先选最大的数，然后就一定能使取的数的数目最小，其实用sort函数就可以了。

弹珠游戏 - 洛谷 这个题是给出一个二维数组，数组中有若干个敌人，其中没有敌人的地方可以容身，此时求在哪个没有敌人的地方容身时，此坐标的同一行与同一列的敌人最多，经典的枚举加贪心，我是直接枚举寻找最大值，但是超时（可能是因为我套了三个for），题解中有个好方法，是直接不用存储在二维数组中，而是把每一行每一列的数据之和相加，再找出最多的敌人数

我的代码如下

#include
using namespace std;
int a[1005][1005];
int main(){
    int n,u=0,maxx=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]==0){
                int b=0;
                u++;
                for(int k=1;k<=n;k++){
                    b+=a[i][k];
                    b+=a[k][j];
                }
                //cout<<"("< 
 
 P1968 美元汇率 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)这个是动态规划和贪心的题，题意是：某人能提前知道汇率的变化，他持有100马克，要将这些钱全部兑换成美元，求能够兑换到的最多美元数。因为给出的天数每天的汇率都不一样，而且还要考虑实数算数运算中进位的误差，也就是说，假设他现在持有马克，当前一天马克兑美元汇率比后一天的马克兑美元汇率低时，就将马克兑换成美元；假设持有美元，当前一天美元兑马克汇率比后一天的美元兑马克汇率低时，就将美元兑换成马克。每次只有两种情况：从前一天直接继承或者兑换，所以只要选择其中更优的一种即可。
 
#include
using namespace std;
int n;
int a[111];
double m=100;
bool check;//check判断是马克还是美元 
int i;
int main(){
	cin>>n;
	for(i=0;i>a[i];
	for(i=0;i 
P2242 公路维修问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 贪心的普及-，有一条道路有N个坑，要对部分路段实施交通管制，求出所需最短的管制路段。给出管制路段的数量，求管制路段的最短距离，其实就是找出各个坑之间的距离然后排序，找到前M-1个最大的距离，以此将路段分成M段，用到了sort和贪心算法，其实也是求最长不管制距离，而且所有被管制的路段的开头和结尾一定都在坑上，才能使浪费达到最小。
 
#include
#include
#include
using namespace std;
int a[20005],b[20005],n,m,ans;
int main(){
    cin>>n>>m>>a[0];
    for(int i=1;i>a[i];
        b[i-1]=a[i]-a[i-1];//算出俩坑之间的距离
    }
    sort(b,b+n);//排出来
    for(int i=0;i 
到底什么是dp思想（内含大量经典例题，附带详细解析）_Y先森0.0的博客-CSDN博客_dp思想 这篇博客写得好。
 
[USACO09OCT]Bessie's Weight Problem G - 洛谷 一道动态规划的题，题意是一只羊要节食，一天只能吃H公斤的草，现在有N捆草，第i捆草有s[i]公斤重，每次吃一捆草的时候都必须把一整捆全吃完，现在求在限制范围内最多可以吃多少公斤的草。这其实也是背包的题，上周看博客的时候看到几篇背包题，这也是一道背包题，这个题其实就是求最多往背包装多少重量
 
#include
#include  
using namespace std;  
int h,n,a;  
int d[50000];  
int main(){  
    cin>>h>>n;
    d[0]=1;  
    for(int i=1;i<=n;i++) {  
         cin>>a;  
         for(int j=h;j>=a;j--){  
             if(d[j-a]){           
                d[j]=1;  
             } 
         }  
    }  
    for(int i=h;i>=0;i--){
        if(d[i]==1){  
           cout<