#include #include #include #include #include #include #include #include #include #include using namespace std; int n; int a[105][105]; int dp[105][105]; int sum[105][105]; int main(){ while(scanf("%d",&n)!=EOF){ for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ scanf("%d",&a[i][j]); } } memset(dp,0,sizeof(dp)); for(int j = 1;j <= n;j++){ // j列的前綴和 for(int i = 1;i <= n;i++){ sum[j][i] = sum[j][i-1] + a[i][j]; } } for(int i = 1;i <= n;i++){ for(int j = i;j <= n;j++){ int right = 0; for(int k = 1;k <= n;k++){ if(right >= 0){ right += sum[k][j] - sum[k][i-1]; } else{ right = sum[k][j] - sum[k][i-1]; } dp[i][j] = max(dp[i][j],right); } } } int ans = -INT_MAX; for(int i = 1;i <= n;i++){ for(int j = i;j <= n;j++){ if(dp[i][j] > ans){ ans = dp[i][j]; } } } cout << ans << endl; } return 0; }
為什麼需要模板?我們已經學過重載(Overloading),
Description有一個三角形木板,豎直立放,上面釘著n
// define head function#ifndef
volatile 是“易變的”、&l
Description'Oh no, they
題目思路O(n)的思路比較簡單,直接用兩個下標掃一遍即可;O