a693. 吞食天地

我們先取得所有食物的飽食度，這時第n個儲存的值代表第n個食物的飽食度，我們用DP的方式讓第n個儲存的值變成第1n個食物的飽食度。

再來就是取範圍，如果我們要從第l個吃到第r個，那代表我們不需要前面1l-1的食物。所以飽食度就等於前r個 減掉前l-1個 。

AC (0.1s, 612KB)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int i,n,m,l,r,sum[100001];
    while(cin>>n>>m){
        for(i=1;i<=n;i++){
            cin>>sum[i];
            sum[i]+=sum[i-1];
        }
        for(i=0;i<m;i++){
            cin>>l>>r;
            cout<<sum[r]-sum[l-1]<<"\n";
        }
    }
    return 0;
}

a272. 猥瑣罐頭下樓梯

Fibonacci數列絕對是DP中最經典，也最簡單的例子。這題我本來打算建表，但看到必須算到2^31-1，我就知道這方法絕對行不通。而選擇不建表，萬一遇到輸入的n很大的時候，電腦又得跑迴圈跑到崩潰。不過討論區有人直接發現當Fibonacci數列 mod 10007，這個數列會是20016個為一循環，太神了，這到底是怎麼發現的，這個發現真的是救了我一命。

AC (2ms, 96KB)

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>

int main(){
    int f[20017]={0},i,n;
    f[1]=1;f[2]=2;
    for(i=3;i<20017;i++){
        f[i] = (f[i-1] + f[i-2])%10007;
    }
    while(scanf("%d",&n) != EOF){
        printf("%d\n",f[n%20016]);
    }
    return 0;
}

封面圖源：AcFun