## Bài 1: [Trò chơi sake](https://marisaoj.com/problem/145)
- :say:
- Trạng thái $f(i)=0/1$ tương ứng với **người đi đầu tiên** nếu có $i$ cốc rượu có thắng hay không.
- Với mỗi trạng thái $f(i)$, đi đến các trạng thái $f(i-A_i)$, nếu không có trạng thái $f(i-A_i)$ nào là trạng thái thua, thì $f(i)$ là trạng thái thua, vì không có cách uống nào để dẫn đối phương đến trạng thái thua. Ngược lại nếu chỉ cần tồn tại một trạng thái thắng thì $f(i)$ sẽ thằng.

Code
:::spoiler

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll a[100001];
bool dp[100001]{};
string winner[2]={"Reimu","Marisa"};
ll minx(ll a,ll b){
	if (a%2==1||b==0) return a;
	return b;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	ll n , m;
	cin >> n >> m  ;
	for (int i=1;i<=m;i++){
		cin >> a[i];
	}
    
	for (int i=0;i<=n;i++) dp[i]=false;

	for (int i=a[1];i<=n;i++){
		bool check=false;
		for (int j=1;j<=m;j++){
			if (a[j]>i) continue;
			if (!dp[i-a[j]]) {
				check=true;
			}
		}

		dp[i]=check;
	}
	if (dp[n]) cout << "Marisa"; else cout << "Reimu";
	
	
	
	
}

:::

## Bài 2: [Một bài toán xây mảng nữa](https://marisaoj.com/problem/146)
- Trạng thái $f(i,j)$, là số lượng dãy đến xây vị trí $i$, và giá trị ở vị trí này là $j$.
- Với mỗi trạng thái $f(i,j)$, cập nhật lên các trạng thái $f(i+1,k)$ mà $j+k$ là số nguyên tố.

Code:
:::spoiler

#include <iostream>
#include <vector>

using namespace std;

const int N = 105, K = 2505, MOD = 1e9 + 7;

int n, k, dp[N][K];
vector<int> primes;
bool is_prime[K];

void sieve(int n) {
    fill(is_prime, is_prime + n, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
}

inline void inc(int &a, int b){
    if((a += b) >= MOD) a -= MOD;
}

int main() {
    cin >> n >> k;
    sieve(2 * k + 1);
    
    for(int i = 0; i <= k; i++){
        dp[1][i] = 1;
    }

    for(int i = 2; i <= n; i++){
        for(int j = 0; j <= k; j++){
            for(int p = 0; p <= k; p++){
                if(is_prime[j + p]){
                    inc(dp[i][p], dp[i - 1][j]);
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i <= k; i++) inc(ans, dp[n][i]);
    cout << ans;
}

:::

## Bài 3: [Trò chơi trên mảng](https://marisaoj.com/problem/148)
- Trạng thái $f(i,j)$ là điểm lớn nhất của người chơi đầu tiên khi mảng chỉ còn các phần tử từ $i$ đến $j$.
- Xét trạng thái $f(i,j)$, khi đó người chơi có thể lấy phần tử $A_i$ hoặc $A_j$:
+ Nếu lấy phần tử $i$, khi đó mảng còn các phần tử từ $i+1$ đến $j$. Lúc này đến lượt người chơi còn lại, sẽ chọn giữa phần tử $i+1$ và $j$, lần lượt có thể dẫn đến các trạng thái $f(i+2,j)$ và $f(i+1,j-1)$, nên người chơi này sẽ chọn trạng thái $T_1 = min(f(i+2,j), f(i+1,j-1))$.
+ Trường hợp còn lại tương tự, có $T_2 = min(f(i,j-2), f(i+1,j-1))$.
+ Cập nhật $f(i,j)= max(A_i+T_1, A_j+T_2)$.

- Có thể đặt trạng thái $f(i,j,0/1)$ là với $0/1$ là lượt của người chơi nào. Trạng thái lưu giá trị lớn nhất hoặc nhỏ nhất tùy lượt người chơi. Làm như này sẽ dễ hiểu hơn.

Code
:::spoiler

#include <bits/stdc++.h> 
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define pb push_back
#define mp make_pair
#define sp(x) fixed<<setprecision(x)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define s 5003
using namespace std;

ll dp[s][s];

ll solve(vector<ll>& a, ll i, ll j)
{
    if(i > j)
    return 0;
    
    if(dp[i][j] != -1)
    return dp[i][j];
    
    ll op1 = a[i] + min( solve(a,i+1,j-1), solve(a,i+2,j));
    ll op2 = a[j] + min( solve(a,i+1,j-1), solve(a,i,j-2));
    
    return dp[i][j] = max(op1,op2);
}

int main()
{
    fast_io;
    
    ll n;
    cin>>n;
    vector<ll> a(n+1);
    
    for(int i=0;i<n;i++)
    cin>>a[i];
    
    memset(dp,-1,sizeof(dp));
    ll X = solve(a,0,n-1);
    
    ll sum = 0;
    for(ll j=0;j<a.size();j++)
    sum += a[j];
    
    ll Y = sum - X;
    cout<<X-Y<<endl;
    
    return 0;
}

:::

## Bài 4: [Tích chập](https://marisaoj.com/problem/149)
- $f(i,j)$, là giá trị lớn nhất với hai dãy con kết thúc lần lượt ở $A_i$ và $B_j$.
- Với trạng thái $f(i,j)$, ta có thể nối vào $f(i-1,j-1)$, bắt đầu một dãy mới với một phần tử $A_i$ và $B_j$, hoặc là bỏ qua. Nghĩa là ta có cập nhật
$$f(i,j)=max(0,f(i-1,j-1)+A_i \times B_j, A_i \times B_j)$$.

Code:
:::spoiler

#include <bits/stdc++.h>

using namespace std;

#define int long long 
#define el '\n'

const int inf = 1e18;
const int md = 1e9+7;

int n, a[5001], b[5001], dp[5001][5001];

signed main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int j = 0; j < n; j++) cin >> b[j];
	int ans = -inf;
	for (int i = 0; i <= n; i++){
		for (int j = 0; j <= n; j++){
			if(i == 0 || j == 0){
				dp[i][j] = 0;
				continue;
			}
			if(dp[i-1][j-1] < 0) dp[i][j] = a[i-1]*b[j-1];
			else dp[i][j] = dp[i-1][j-1] + a[i-1]*b[j-1];	
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans << el;
	return 0;
};

:::