1.月度开销
题目：
农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来\(N(1<=N<=100000)\)天里每天需要的开销。
约翰打算为连续的\(M(1<=M<=N)\)个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。
约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。
题目条件：
1.输入第一行包含两个整数N,M,用单个空格隔开。
2.接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。
3.输出最大月度开销的最小值。
分析：
可以二分枚举答案，用二分来枚举这个最小值，接下来用一个函数来判断这个值能不能做到，check函数就是从左到右贪心，每当加上一个数就会超过这个值时就分一段，最后看一看分的段数大还是M大即可。如果分的数量比M少就说明分M段也可以，只要段数小于等于M即可。
程序：
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100001],l,r;
bool check(long long x)
{long long sum=0,k=0;for(int i=1;i<=n;i++){if(sum+a[i]>x){sum=0;k++;}sum+=a[i];if(i==n)k++;}if(k<=m)return 1;return 0;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];r+=a[i];l=max(l,a[i]);}while(l<r){long long mid=(l+r)/2;if(!check(mid))l=mid+1;elser=mid;}cout<<l<<endl;return 0;
}
2.道具商店
题目：
道具商店里有n件道具可供挑选。第i件道具可为玩家提升\(a_i\)点攻击力，需要\(c_i\)枚金币才能购买，每件道具只能购买一次。现在你有k枚金币，请问你最多可以提升多少点攻击力？
题目条件：
第一行，两个正整数n，k表示道具数量以及你所拥有的金币数量。接下来n行，每行两个正整数\(a_i\),\(c_i\)表示道具所提升的攻击力点数，以及购买所需的金币数量。对于所有测试点，保证\(1<=N<=500,1<=k<=10^9,1<=a_i<=500,1<=c_i<=10^9\)。
分析：
这道题目K过大，不能直接用01背包，数组也开不下，由于我们发现\(a_i\)的范围异常地小，我们可以把攻击力作为第二个参数，这样就能做了。f[i][i]表示前i个道具里面加起来攻击力为j需要多少的金币。
程序：
#include<bits/stdc++.h>
using namespace std;
int n,k,m,a[501],b[501],f[501][250001];
int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];m+=a[i];}for(int i=0;i<=n;i++)for(int j=1;j<=m;j++)f[i][j]=1e9;for(int i=1;i<=n;i++)for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=a[i])f[i][j]=min(f[i][j],f[i-1][j-a[i]]+b[i]);}for(int i=m;i>=0;i--)if(f[n][i]<=k){cout<<i<<endl;break;}return 0;
}
最长上升子序列（大数据）
题目：
给你n个整数，求出最长上升子序列长度。n最大是10万。
题目条件：
无。
分析：
普通的最大上升子序列的时间复杂度约等于\(n^2\)，但这里n有10万，不能用普通的做法。我们发现这个序列是有单调性的，序列本身的元素是递增的，我们只需要每次来查找，有一个k来统计序列里已经有多少个了，最后k就是答案，如果当前这个元素比序列末尾的元素大，那就直接放进去，否则就在b数组里面查找第一个大于等于a[i]的元素，把a[i]放进去即可。
#include<bits/stdc++.h>
using namespace std;
int n,a[100001],b[100001],k=1;
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];b[1]=a[1];for(int i=2;i<=n;i++){if(a[i]>b[k])b[++k]=a[i];else{int l=1,r=k;while(l<r){int mid=(l+r)/2;if(b[mid]<a[i])l=mid+1;elser=mid;}b[l]=a[i];}}cout<<k<<'\n';return 0;
}