【noip2013】序列重排：

全局数组变量 a 定义如下：

const int SIZE=100; 
int a[SIZE],n;

它记录着一个长度为 n 的序列 a[1] ，a[2] ，… ， a[n] 。现在需要一个函数，以整数 p(1 ≤p≤ n) 为参数， 实现如下功能： 将序列 a 的前 p 个数与后 n-p 个数对调， 且不改变这 p 个数（或 n-p 个数）之间的相对位置。例如，长度为 5 的序列 1， 2，3，4，5，当 p=2 时重排结果为 3，4， 5，1，2。有一种朴素的算法可以实现这一需求，其时间复杂度为 O(n) 、空间复杂度为 O(n)

可以用时间换空间，使用时间复杂度为O(n^2)、空间复杂度为 O(1) 的算法：

本题答案：

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 100;
int a[SIZE] , n; 
void swap(int p){
    int i,j,temp;
    for(i = p+1 ; i <= n; i ++){
        temp = a[i];
        for(j = i ; j >= i-p+1 ; j --){
            a[j] =a[j-1];
        }
        a[i-p] = temp; 
    }
}
int main(){
    int p;
    cin >> n >> p;
    for (int i = 1 ; i <= n ; i ++){
        cin >> a[i];
    }
    swap(p);
    for (int i = 1 ; i <= n ; i ++){
        cout <<  a[i];
    }
    return 0;
}

【noip2014】最大子矩阵：

给出 m行 n列的整数矩阵，求最大的子矩阵和(子矩阵不能为空)。 输入第一行包含两个整数 m和 n，即矩阵的行数和列数。之后 m行，每行 n个整数，描述整个矩阵。程序最终输出最大的子矩阵和。

本题答案：

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 100;
int matrix[SIZE+1][SIZE+1];
int rowsum[SIZE+1][SIZE+1];
int m, n, i, j, first, last, area, ans;
int main(){
    scanf("%d",&n);
    m=n;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++){
            scanf("%d", &matrix[i][j]);
        }
    ans = matrix[1][1];
    for (i = 1; i <= m; i++)
        rowsum[i][0]=0;
            for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            rowsum[i][j] = rowsum[i][j-1]+matrix[i][j];
                for (first = 1; first <= n; first++)
        for (last = first; last <= n; last++){
            area=0;
            for (i = 1; i <= m; i++) {
                area += rowsum[i][last] -rowsum[i][first-1];
                if (area > ans) ans = area;
            }
        }
    printf("%d\n", ans);
    return 0;
}