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();
}
acm.rar （41个子文件） 
模板 
bzoj1722.txt 141B
img-503093712-0012.jpg 253KB
BSGS.cpp 973B 二分图最大匹配_匈牙利.cpp 686B FFT.cpp 2KB 欧拉回路.cpp 2KB 求原根.cpp 678B KD树.cpp 2KB 2876.cpp 872B 块状树.cpp 948B 可持久化treap.cpp 3KB 高精度模板.cpp 4KB 后缀数组.cpp 1KB 快速乘.cpp 197B cdq.cpp 3KB bzoj1723.txt 2KB KMP.cpp 481B 输入输出优化.cpp 665B treap.cpp 1KB hash.cpp 416B splay.cpp 2KB UOJ模板题库.txt 154B treap非旋转.cpp 3KB 函数式线段树.cpp 2KB 带花树.cpp 2KB MY单纯形.cpp 2KB vijos1003用分治解决表达式计算问题 小浮点数检验法 浮点数比较.cpp 3KB 树链剖分.cpp 3KB 块状链表editor.cpp 3KB LCT.cpp 3KB 计算几何.cpp 3KB bitset.cpp 1KB 虚树.cpp 640B 后缀自动机.cpp 605B bzoj1598【k短路Astar】.cpp 2KB 数论.cpp 3KB 单纯形.cpp 1KB 莫队_小Ｚ的袜子.cpp 1KB 树上莫队带修改_糖果公园.cpp 3KB 模拟退火.cpp 782B 莫比乌斯反演.cpp 504B资源评论
