acm.rar_KFOI_acm 比赛 cpp_algorithm_mirrorm5y_信息学竞赛

bzoj1723 usaco银组题，但通过率极低。因为有一种特殊情况很容易漏掉。 下次自己做做看 #include <iostream> using namespace std; #define MAX 800 #define MIN -1000000000 int n,mat[MAX][MAX],array[MAX],maxsum=MIN; // read input void fRead() { cin >> n; for (int i=0; i<n; i++) for (int j=0; j<n; j++) cin >> mat[i][j]; } // write output void fWrite() { cout << maxsum << "\n"; } // scan circular array for the maximal-sum subsequence // scan the array once: O(n) void scan() { int sum=MIN; // circular scan for (int i=0,x=0,t=0; i<x+n; i++) { t+=array[i%n]; if (sum<t) sum=t; // update maximal-sum in the sequence // if current sum is less than 0, // start a new sub sequence at the current location if (t<0) if (i>=n) break; else t=0,x=i+1; } if (maxsum<sum) maxsum=sum; } // special case: when all the numbers is in the sequence // remove the maximal negative-sum subsequence from the array; void special() { // find maximal negative-sum subsequence int sum=0,neg=0; for (int i=0; i<n; i++) { sum+=array[i]; if (neg>sum) neg=sum; if (sum>0) sum=0; } // total sum of the array sum=0; for (int i=0; i<n; sum+=array[i++]); if (sum!=neg) sum-=neg; // exclude maximal negative-sum subsequence if (maxsum<sum) maxsum=sum; } // scan matrix in 4 directions: // horizontal, vertical, left diagonal, right diagonal void solve(int dir) { for (int i=0; i<n; i++) { int y=dir==2 ? 0 : i; int x=dir==2 ? i : 0; // extract the array in given direction for (int j=0; j<n; j++) { array[j]=mat[y][x]; if (dir==1 || dir==3) x=(x+1)%n; else if (dir==4) x=(x-1+n)%n; if (dir>1) y=(y+1)%n; } scan(); special(); } } int main() { fRead(); for (int i=1; i<=4; solve(i++)); fWrite(); }