Codeforces DP 练习

87 阅读 0 评论 58 点赞

我是靠谱客的博主内向火，最近开发中收集的这篇文章主要介绍Codeforces DP 练习，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Codeforces 466 C. Number of Ways【前缀】

You've got array a[1], a[2], ..., a[n], consisting of n integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same.

More formally, you need to find the number of such pairs of indices i, j (2 ≤ i ≤ j ≤ n - 1), that $\text{[math]}$ .

Input

The first line contains integer n (1 ≤ n ≤ 5·105), showing how many numbers are in the array. The second line contains n integers a[1], a[2], ..., a[n] (|a[i]| ≤ 109) — the elements of array a.

Output

Print a single integer — the number of ways to split the array into three parts with the same sum.

   Examples 
 
     input 
    
      Copy 
    
5
1 2 3 0 3

     output 
    
      Copy 
    
2

     input 
    
      Copy 
    
4
0 1 -1 0

     output 
    
      Copy 
    
1

     input 
    
      Copy 
    
2
4 1

     output 
    
      Copy 
    
0

思路：我们可以求前缀和，然后我们的目标找到a[ i ]*3 = a[n - 1] && a[ j ]*3 = a[n - 1]*2;

那么我们想一下之前记录一下a[i]*3 = a[n - 1]的个数，那么只需要遇到a[ j ]*3 = a[n - 1]*2把之前的加到总的sum中就可以了。。。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;
const int maxn = 5e5+7;
int n;
ll a[maxn], sum = 0, ans = 0;

int main()
{
    memset(a, 0, sizeof(a));
    scanf("%d",&n); scanf("%lld", &a[0]);
    for(int i = 1; i < n; i++) scanf("%lld", &a[i]), a[i] += a[i - 1];
    if(a[n - 1]%3) printf("0n");
    else {
            for(int i = 0; i < n - 1; i++)
            {
                if(a[i]*3 == a[n - 1]*2) sum += ans;
                if(a[i]*3 == a[n - 1]) ans++;
            }
            printf("%lldn", sum);
    }
    return 0;
}

Codeforces 368 B. Sereja and Suffixes

Sereja has an array a, consisting of n integers a1, a2, ..., an. The boy cannot sit and do nothing, he decided to study an array. Sereja took a piece of paper and wrote out m integers l1, l2, ..., lm (1 ≤ li ≤ n). For each number li he wants to know how many distinct numbers are staying on the positions li, li + 1, ..., n. Formally, he want to find the number of distinct numbers among ali, ali + 1, ..., an.?

Sereja wrote out the necessary array elements but the array was so large and the boy was so pressed for time. Help him, find the answer for the described question for each li.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105) — the array elements.

Next m lines contain integers l1, l2, ..., lm. The i-th line contains integer li (1 ≤ li ≤ n).

Output

Print m lines — on the i-th line print the answer to the number li.

   Examples 
 

     input 
    
      Copy 
    
10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10

     output 
    
      Copy 
    
6
6
6
6
6
5
4
3
2
1

思路：要查询后缀中不同数字的个数，直接后缀和计算就好了。。。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long

using namespace std;
const int maxn = 1e5+9;

int ans = 0, n, m, a[maxn], sum[maxn];
bool v[maxn];

int main()
{
    memset(v, 0, sizeof(v));
    memset(sum, 0, sizeof(sum));
    scanf("%d%d",&n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = n - 1; i >= 0; i--) {
        if(!v[a[i]]) {
            v[a[i]] = true;
            ans++;
        }
        sum[i] = ans;
    }

    for(int i  = 0; i < m; i++)
    {
        int l; scanf("%d", &l);
        printf("%dn",sum[l - 1] - sum[n]);
    }
    return 0;
}

Codeforces 651 A. Joysticks

Friends are going to play console. They have two joysticks and only one charger for them. Initially first joystick is charged at a1 percent and second one is charged at a2 percent. You can connect charger to a joystick only at the beginning of each minute. In one minute joystick either discharges by 2 percent (if not connected to a charger) or charges by 1 percent (if connected to a charger).

Game continues while both joysticks have a positive charge. Hence, if at the beginning of minute some joystick is charged by 1 percent, it has to be connected to a charger, otherwise the game stops. If some joystick completely discharges (its charge turns to 0), the game also stops.

Determine the maximum number of minutes that game can last. It is prohibited to pause the game, i. e. at each moment both joysticks should be enabled. It is allowed for joystick to be charged by more than 100 percent.

Input

The first line of the input contains two positive integers a1 and a2 (1 ≤ a1, a2 ≤ 100), the initial charge level of first and second joystick respectively.

Output

Output the only integer, the maximum number of minutes that the game can last. Game continues until some joystick is discharged.

   Examples 
 
     input 
    
      Copy 
    
3 5

     output 
    
      Copy 
    
6

     input 
    
      Copy 
    
4 4

     output 
    
      Copy 
    
5

Note

In the first sample game lasts for 6 minute by using the following algorithm:

at the beginning of the first minute connect first joystick to the charger, by the end of this minute first joystick is at 4%, second is at 3%;
continue the game without changing charger, by the end of the second minute the first joystick is at 5%, second is at 1%;
at the beginning of the third minute connect second joystick to the charger, after this minute the first joystick is at 3%, the second one is at 2%;
continue the game without changing charger, by the end of the fourth minute first joystick is at 1%, second one is at 3%;
at the beginning of the fifth minute connect first joystick to the charger, after this minute the first joystick is at 2%, the second one is at 1%;
at the beginning of the sixth minute connect second joystick to the charger, after this minute the first joystick is at 0%, the second one is at 2%.

After that the first joystick is completely discharged and the game is stopped.

思路：给定两个数字a,b;每次，只有一个数字能够充电，充电只能加1，而不充电就要减2，问最多的次数。。。直接贪心吧。。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
int a, b, sum = 0;


int main()
{
    scanf("%d%d",&a, &b);
    if(a<b) swap(a, b);
    while(a>2||b>2)
    {
        int p = a/2;
        if(a%2 == 0) p--; a -= 2*p;
        b += p; sum += p;
        if(a<b) swap(a, b);
    }
    if(a==2||b==2) sum++;
    printf("%dn", sum);
    return 0;
}

Codeforces 363 B. Fence

There is a fence in front of Polycarpus's home. The fence consists of n planks of the same width which go one after another from left to right. The height of the i-th plank is hi meters, distinct planks can have distinct heights.

$\text{[math]}$ Fence for n = 7 and h = [1, 2, 6, 1, 1, 7, 1]

Polycarpus has bought a posh piano and is thinking about how to get it into the house. In order to carry out his plan, he needs to take exactly k consecutive planks from the fence. Higher planks are harder to tear off the fence, so Polycarpus wants to find such k consecutive planks that the sum of their heights is minimal possible.

Write the program that finds the indexes of k consecutive planks with minimal total height. Pay attention, the fence is not around Polycarpus's home, it is in front of home (in other words, the fence isn't cyclic).

Input

The first line of the input contains integers n and k (1 ≤ n ≤ 1.5·105, 1 ≤ k ≤ n) — the number of planks in the fence and the width of the hole for the piano. The second line contains the sequence of integers h1, h2, ..., hn (1 ≤ hi ≤ 100), where hi is the height of the i-th plank of the fence.

Output

Print such integer j that the sum of the heights of planks j, j + 1, ..., j + k - 1 is the minimum possible. If there are multiple such j's, print any of them.

   Examples 
 
     input 
    
      Copy 
    
7 3
1 2 6 1 1 7 1

     output 
    
      Copy 
    
3

Note

In the sample, your task is to find three consecutive planks with the minimum sum of heights. In the given case three planks with indexes 3, 4 and 5 have the required attribute, their total height is 8.

思路：就是要找最大的k子序列的最小值。。。贪心暴力实现。。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 2e5+7;

int n, k, ans[maxn], minsum = 1e9+7, p = -1;


int main()
{
    memset(ans, 0, sizeof(ans));
    scanf("%d%d",&n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &ans[i]), ans[i] += ans[i - 1];
    for(int i = k; i <= n; i++) {
        if(ans[i] - ans[i - k] < minsum) {
            minsum = ans[i] - ans[i - k];
            p = i - k + 1;
        }
    }
    printf("%dn", p);
    return 0;
}

Codeforces 702 A. Maximum Increase

You are given array consisting of n integers. Your task is to find the maximum length of an increasing subarray of the given array.

A subarray is the sequence of consecutive elements of the array. Subarray is called increasing if each element of this subarray strictly greater than previous.

Input

The first line contains single positive integer n (1 ≤ n ≤ 105) — the number of integers.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print the maximum length of an increasing subarray of the given array.

   Examples 
 
     input 
    
      Copy 
    
5
1 7 2 11 15

     output 
    
      Copy 
    
3

     input 
    
      Copy 
    
6
100 100 100 100 100 100

     output 
    
      Copy 
    
1

     input 
    
      Copy 
    
3
1 2 3

     output 
    
      Copy 
    
3

思路：求最长递增连续子序列，简单的题目。。。

代码：

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long

using namespace std;
const int maxn = 1e5+7;
int n, a[maxn], dp[maxn], ans = 1;


int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) dp[i] = 1;
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    for(int i = 1; i < n; i++) {
            if(a[i] > a[i - 1]) dp[i] = dp[i - 1] + 1;
            ans = max(ans, dp[i]);
    }
    printf("%dn",ans);
    return 0;
}