TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270)

D - Stones

贪心   ×

dp     √

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 400 points

Problem Statement

Takahashi and Aoki will play a game of taking stones using a sequence (A1​,…,AK​).

There is a pile that initially contains N stones. The two players will alternately perform the following operation, with Takahashi going first.

• Choose an Ai​ that is at most the current number of stones in the pile. RemoveAi​ stones from the pile.

The game ends when the pile has no stones.

If both players attempt to maximize the total number of stones they remove before the end of the game, how many stones will Takahashi remove?

 

Constraints

• 1≤N≤10^4
• 1≤K≤100
• 1=A1​
• All values in the input are integers.

 

Input

The input is given from Standard Input in the following format:

N K
A1 A2      AK

Output

Print the answer.

---

Sample Input 1 Copy

10 2
1 4

Sample Output 1 Copy

5

Below is one possible progression of the game.

• Takahashi removes 4 stones from the pile.
• Aoki removes 4 stones from the pile.
• Takahashi removes 1 stone from the pile.
• Aoki removes 1 stone from the pile.

In this case, Takahashi removes 5 stones. There is no way for him to remove 6 or more stones, so this is the maximum.

Below is another possible progression of the game where Takahashi removes 5 stones.

• Takahashi removes 1 stone from the pile.
• Aoki removes 4 stones from the pile.
• Takahashi removes 4 stones from the pile.
• Aoki removes 1 stone from the pile.

---

Sample Input 2 Copy

11 4
1 2 3 6

Sample Output 2 Copy

Copy

8

Below is one possible progression of the game.

• Takahashi removes 6 stones.
• Aoki removes 3 stones.
• Takahashi removes 2 stones.

In this case, Takahashi removes 8 stones. There is no way for him to remove 9 or more stones, so this is the maximum.

---

Sample Input 3 Copy

10000 10
1 2 4 8 16 32 64 128 256 512

Sample Output 3 Copy

5136

 

#include <bits/stdc++.h>
using namespace std;
typedef double db;
#define int long long
int dp[10010];
int a[110];
int n,k;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(a[j]>i)break;
            dp[i]=max(dp[i],i-dp[i-a[j]]);
        }
    }
    cout<<dp[n]<<"\n";
 
    return 0;
}

 贪心反例：
 

10 3
1 3 4

最大值是6而不是4