Question

能把杭电acm1005题 解释下么 我自己是递归编的程序，网上看了好多说要求周期，，，不懂啊

Answer 1

因为n太大，所以如果采用递归或者迭代的思路，会出现超时的情况，因此这实际上是一道找规律的题目

从迭代函数f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7可以看出，f(n-1)的取值可能有7种，f(n-2)也有7种，故f(n-1)f(n-2)的组合可能有49种，于是可以得到，在49次迭代内f(n)必有规律可寻，这便是此题的核心思路。值得注意的是，规律不一定是从1 1开始，因为序列可能是1 1 2 3 2 3……，因此我们在每次迭代之后必须从第一个数遍历到当前迭代数，来得到规律开始的地方及规律的周期。

附上代码

#include<stdio.h>
#include<stdlib.h>int main() {
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        int n;
        int *s, *sum, max;
        int a, b, A, B;
        scanf("%d", &n);
        s = (int *)malloc(sizeof(int) * n);
        sum = (int *)malloc(sizeof(int) * n);
        for(int j = 0; j < n; j++) {
            scanf("%d", &s[j]);
            sum[j] = 0;
        }
        if(i != 0) {
            printf("\n");
        }
        max = sum[0] = s[0];
        A = B = a = b = 0;
        for(int j = 1; j < n; j++) {
            if(sum[j - 1] + s[j] >= s[j]) {
                sum[j] = sum[j - 1] + s[j];
                b++;
            } else {
                sum[j] = s[j];
                a = b = j;
            }
            if(sum[j] > max) {
                max = sum[j];
                A = a;
                B = b;
            }
        }
        printf("Case %d:\n%d %d %d\n", i+1, max, A + 1, B + 1);
    }
    return 0;}

欢迎追问，满意请采纳，谢谢