从左上角走到右下角，能走两次，问你最大收益，两条路如果走到同一个点就只有一份收益
特殊情况就是两条路重复的时候，重复的必要条件是两条路走的步数相等，为了方便维护这个值，DP维护的状态中保存当前走的总步数和第一二条路向右走的步数，这样向下走的步数可以直接计算出，状态转移就很明显了就
/* dp[i1][i2][k]: 第一个点走到(i1,k-i1),第二个点走到(i2,k-i2)的最大值 dp[i1][i2][k] 可由 dp[i1][i2][k-1],dp[i1-1][i2][k-1],dp[] */ int mp[111][111]; int dp[22][22][44]; void solve() { int n;cin>>n; int x,y,z; while(cin>>x>>y>>z&&(x|y|z)) mp[x][y]=z; int ans=0; for(int k=2;k<=n+n;++k) for(int i1=1;i1<min(n+1,k);++i1) for(int i2=1;i2<min(n+1,k);++i2) { int tmp=(i1==i2?mp[i1][k-i1]:mp[i1][k-i1]+mp[i2][k-i2]); dp[i1][i2][k]=tmp+max(max(dp[i1-1][i2][k-1],dp[i1][i2-1][k-1]),max(dp[i1][i2][k-1],dp[i1-1][i2-1][k-1])); if(k==n+n) ans=max(ans,dp[i1][i2][k]); } cout<<ans<<endl; }找长不超过m的最大子段和 区间和，考虑前缀和，对于对于每一个右端点，找一个最小的左端点，且长度在m内，使用单调队列 队列中越靠近队头的元素，越早入队
int a[MX]; void solve() { int n,m;cin>>n>>m; deque<pair<int,int>>q;//维护一个单调递增队列 int ans=-0x3f3f3f; rpp(i,n) cin>>a[i],ans=max(ans,a[i]),a[i]+=a[i-1]; q.push_back(make_pair(0,0)); rpp(i,n) { while(q.size()&&i-q.front().first>m) q.pop_front(); if(q.size()) ans=max(ans,a[i]-q.front().second); while(q.size()&&q.back().second>=a[i]) q.pop_back(); q.push_back(make_pair(i,a[i])); } cout<<ans<<endl; }O(nlhn)的LIS，维护每个长度的上升子序列末尾的最小值 整个代码都很精妙）%%%%
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main(void) { int n; cin >> n; vector<int>arr(n); for (int i = 0; i < n; ++i)cin >> arr[i]; vector<int>stk;//模拟堆栈 stk.push_back(arr[0]); for (int i = 1; i < n; ++i) { if (arr[i] > stk.back())//如果该元素大于栈顶元素,将该元素入栈 stk.push_back(arr[i]); else//替换掉第一个大于或者等于这个数字的那个数 *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i]; } cout << stk.size() << endl; return 0; }