T1
原題鏈接https://www.luogu.com.cn/problem/P1025
不是我出的

T2
原題鏈接：https://www.luogu.com.cn/problem/P26787
這道題就是講過的二分+貪心，先二分規定每兩個點之間都必須大于等于某個值，然后依次枚舉通過貪心求出最少需要刪除的點數，最后用這個最小值和m比較一下即可。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){x=0;int f=0;char s=getchar();while(!isdigit(s))f|=s=='-',s=getchar();while(isdigit(s))x=x*10+s-48,s=getchar();x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){if(x<0)putchar('-'),x=-x;do{buf[++cc]=int(x%10);x/=10;}while(x);while(cc)putchar(buf[cc--]+'0');
}
const int N=5e4+10;
int L,n,m,a[N];
bool check(int lim){int last=0,cnt=0;rep(i,1,n){if(a[i]-last<lim)cnt++;else last=a[i];}if(L-last<lim)cnt++;return cnt<=m;
}
void solve(){qr(L),qr(n),qr(m);rep(i,1,n)qr(a[i]);int l=1,r=L,mid,ans=0;while(l<=r){mid=(l+r)/2;if(check(mid))l=mid+1,ans=mid;else r=mid-1;}qw(ans);
}
int main(){int tt;tt=1;while(tt--)solve();return 0;
}

T3
原題鏈接：https://www.luogu.com.cn/problem/P1149
不是我出的

T4
高中的時候師兄出的題，不過我把簡單版拿出來考大家，原來的版本不止一塊糕，有興趣的同學可以思考。

猜測有不少人會用能切多大切多大的策略，但是這樣確實是不正確的，提交發現答案錯誤以后應該是可以發現的。

正確的思路就是先考慮$n?1$和$1?m$這兩種糕，這兩種糕顯然都滿足前面那個貪心，這就說明如果不橫切只豎切的話，切法是固定的。

觀察可以發現，每切一次一邊的長度大概會減少一半，也就是說橫切和豎切的刀數最多也就是30~40，如果超過了就會切成長度為1的。

結合這兩種思路，我們枚舉橫切的刀數，剩下的刀數全部用來豎切，拿一個數組記錄每一邊切多少刀以后還會剩下多少，然后統計即可。時間復雜度為$O(TlogN)$。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){x=0;int f=0;char s=getchar();while(!isdigit(s))f|=s=='-',s=getchar();while(isdigit(s))x=x*10+s-48,s=getchar();x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){if(x<0)putchar('-'),x=-x;do{buf[++cc]=int(x%10);x/=10;}while(x);while(cc)putchar(buf[cc--]+'0');
}
const int N=110;
int n,m,k;
int cnt1,f[N];
int cnt2,g[N]; 
void solve(){qr(n),qr(m),qr(k);f[cnt1=0]=n;while(f[cnt1]>1){cnt1++;f[cnt1]=(f[cnt1-1]+1)/2;}g[cnt2=0]=m;while(g[cnt2]>1){cnt2++;g[cnt2]=(g[cnt2-1]+1)/2;}ll ans=0;rep(i,0,min(cnt1,k)){int j=min(cnt2,max(0,k-i));ans=max(ans,1ll*n*m-1ll*f[i]*g[j]);}qw(ans);puts("");
}
int main(){    int tt;qr(tt); while(tt--)solve();return 0;
}

T5
fyh大神出的
原題鏈接：https://www.luogu.com.cn/problem/P3974
這是fyh大神的思路

#include <cstdio>
const int CN = 1010;
int T, N, M, a[CN][CN];
long long f[CN][CN];
long long max(long long a, long long b, long long c) {if (a > b)return a > c ? a : c;return b > c ? b : c;
}
int main() {scanf("%d", &T);while (T--) {scanf("%d%d", &N, &M);for (int i = 1; i <= N; ++i)for (int j = 1; j <= M; ++j)scanf("%d", &a[i][j]);for (int i = N; i >= 1; --i)for (int j = 1; j <= M; ++j)f[i][j] = max(f[i + 1][j - 1] + a[i][j], f[i + 1][j], f[i][j - 1]);printf("%lld\n", f[1][M]);for (int i = 1; i <= N; ++i)for (int j = 1; j <= M; ++j)f[i][j] = 0;}return 0;
}

洛谷上應該有這種做法的講解，說實話我也感覺很震驚，也不太理解。

下面講一下我的貪心法，這種做法實際上就是一行一行模擬路徑的選擇，大家可以自己模擬一下，這個模擬過程確實挺復雜的。

首先考慮一行的情況，很明顯就是取最大值。

然后考慮兩行的情況，我的思路是在第一行已經確定路徑的基礎上將第二行加上，如果只靠第一行的路徑沒有辦法滿足第二行的全部需求，那么我們再給第二行添上能夠恰好滿足條件的路徑，這些路徑顯然是先下到第二行再往右邊走。對于第一行原本的路徑，我采用的是能往下就往下的做法，比如當前已經有x跳路徑到達$(1,i)$，但是$(1,i)$右邊的最大值mx小于x，那么就可以把x-mx的路徑提前往下走，剩下的路徑顯然是可以滿足要求的。

現在拓展到一般情況，假設現在要把第i行插入矩陣，其中$f[i][j]$表示剛好到達$(i,j)$的路徑條數，這些路徑剛好就是從第$i?1$行直接下來的。

那么我們馬上就要考慮需要額外引入多少條路徑，這些路徑就是從起點直接下到$(i,1)$。這個值是$max(0,max(a[i][j]?{\sum }_{k=1}^{j}f[i][k]))$，也就是最糟糕的情況是把下來的全部路徑拉到右邊，如果這不能滿足要求，那就要額外引入路徑。

然后的操作就是從左往右枚舉點$(i,j)$，顯然我們要在每一個點都讓最多的路徑往下，使得剩下的路徑在全部往右走的情況下能夠滿足每一個點的要求，具體實現大家可以自己去想，不過思路都是一樣的，這里只是提供其中實現方法。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){x=0;int f=0;char s=getchar();while(!isdigit(s))f|=s=='-',s=getchar();while(isdigit(s))x=x*10+s-48,s=getchar();x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){if(x<0)putchar('-'),x=-x;do{buf[++cc]=int(x%10);x/=10;}while(x);while(cc)putchar(buf[cc--]+'0');
}
const int N=1e3+10;
const ll inf=1e18;
int n,m,a[N][N];
ll f[N][N],sum[N][N],nd[N][N],mx[N][N];
void solve(){qr(n),qr(m);rep(i,1,n)rep(j,1,n)qr(a[i][j]);rep(i,1,n)rep(j,1,n)f[i][j]=sum[i][j]=0;ll ans=0;rep(i,1,n){rep(j,1,m){sum[i][j]=sum[i][j-1]+f[i][j];nd[i][j]=a[i][j]-sum[i][j];}mx[i][m+1]=-inf;dwn(j,m,1)mx[i][j]=max(mx[i][j+1],nd[i][j]);ans+=max(0ll,mx[i][1]);ll add=max(0ll,mx[i][1]);rep(j,1,m){if(add>mx[i][j+1]){ll maxflow=min(add+sum[i][j],add-mx[i][j+1]);f[i+1][j]+=maxflow;add-=maxflow;}}}qw(ans);puts("");
}
int main(){int tt;qr(tt);while(tt--)solve();return 0;
}