Problem - C - Codeforces 題意： 給一堆節點，表示節點上有寶石，重複輸入節點代表有多少寶石，和一開始跳躍的距離 D，代表初始時在 D 編號的島上，且最後一次跳躍的距離是 D。接著每次移動可以選擇移動最後一次移動的長度 -1 / 0 / +1，但不能不移動( 移動…

Problem - 375B - Codeforces 題意： 給一個 0/1 矩陣，求最大全 1 矩形面積。 解法： 先預處理 dp[ i ][ j ] : 在 row i, col j, 向右延伸連續 1 的最長長度。 接著對於每個固定左界，將每一行收集起來，由大到小排序。這時候就能 O( N ) 更新答案。 int N,…

Problem - 269B - Codeforces 題意： 給一堆東西的編號和位置，保證輸入位置是由小到大，操作可以將任意一個東西移到任意一個地方，求最少操作數使編號隨位置非嚴格遞增。 解法： 就是 N - LIS。 int N, M; vi S; vd X; void init(){ cin >> N >> M; S = vi(…

Problem - 660C - Codeforces 題意： 給 0, 1 組成的序列，求修改至多 K 個數字之後的最長連續 1 子序列長度，及整體長相。 解法： 預處理前綴和，接著二分搜答案。每次確認答案是否對只需要 O( N )。 int N, K; vi A; void init(){ cin >> N >> K; A = vi( …

Problem - C - Codeforces 題意： 給一個有向無環圖，保證 1 到 N 連通，有邊權。求不超過給定 T 的總邊權下，由 1 移動到 N 最多可以經過多少不同節點，以及其路徑。 解法： dp[ i ][ j ] : 最後在 i 號節點，已拜訪 j 個節點。 因為拜訪過的節點不可能再被…