Compartir y extraño pizza

Question

Aquí es un problema clásico, que cada matemático se han visto al menos onece en su vida:

Anne y Ben están compartiendo una pizza. La pizza se divide en un número de piezas de dimensiones desiguales. Anne toma la primera división, y luego de que ella y Ben alternativo, siempre tomando en rodajas adyacente a la creación del agujero (de modo que la parte restante de la pizza permanece conectado). Puede Anne siempre es garantía de que ella consigue al menos tanto pizza como Ben?

Si usted no ha visto esto, sin embargo, usted tal vez quiera darle un minuto de reflexión. Sugerencia: la solución es sencilla y elegante. Es útil para separar la pizza en "par" e "impar" de piezas.

Pregunta: ¿Qué sucede cuando la pizza está dividido en un extraño número de piezas?

Claramente, para $3$ piezas Alice puede garantizar a comer $\geq 1/2$ de la pizza (pero no puede, en general, hacen mejor). ¿Esta siendo cierto en general?

Answer 1

Tal vez esto ayuda a: Que le den la rebanadas de pizza y se le da la máxima cantidad de pizza que jugador $A$ puede garantizar.

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

int A[100];

int maxline( vector <int> V){ //this solves the problem when the slices are in a line
    int N=V.size();
    int M[100][100]; //M[i][j] stores the max pizza amount 
                    //when we only consider slices i,i+1...i+j-1
    for(int i=1;i<=N;i++){
        for(int j=0;j+i-1<N;j++){ //here we fill the matrix recursively with linear programming
            if(i==1) M[j][i]=V[j];
            if(i==2) M[j][i]= max(V[j],V[j+1]);
            if(i>2) M[j][i]= max( V[j] + min(M[j+2][i-2],M[j+1][i-2]), V[j+i-1]+min(M[j][i-2],M[j+1][i-2]));
        }
    }
    return(M[0][N]);
}

int main(){
    int N,T=0,res=0;
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d",&A[i]);
        T+=A[i];
    }
    for(int i=0;i<N;i++){ // this just iterates over all possible first picks.
        vector <int> V;
        for(int j=(i+1)%N;j!=i;j=(j+1)%N){
            V.push_back(A[j]);
        }
        res=max(res,T-maxline(V));
    }
    printf("%d\n",res);
}