Nella gara PreOII, ho cercato di risolvere il problema scontri usando una dinamica usando una tecnica simile a quella che serve per risolvere il problema “Somme di sequenze”. Il fatto è che a quanto ho saputo, dei miei amici hanno implementato la stessa idee prendendo 77, mentre io mi sono stampato contro dei WA fin dal primo testcase.
Il codice è questo:
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <utility>
#include <stdio.h>
#include <queue>
#include <fstream>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <bitset>
#include <string.h>
#define MAX_N 5000
#define INF 99999999
#define N_CHAR 130
using namespace std;
typedef pair<int, int> ii ;
typedef vector< ii > vii ;
typedef vector<int> vi ;
int N, freccia[MAX_N],memo[MAX_N][MAX_N];
int dp(int start, int end){
int count = 0;
if(start >= end)
return INF;
if(memo[start][end]!=-1)
return memo[start][end];
for(int i=start;i<end;i++){
if(i<(start+end)/2)
count += abs(freccia[i]-0);
else
count +=abs(freccia[i]-1);
}
int sol = count;
for(int i=start+2;i<=end-2;i+=2)
sol = min(sol, dp(start,i) + dp(i, end));
//cout <<start<<" "<<end<<" "<<sol<<endl;
return memo[start][end] = sol;
}
int Gira(int N, int *freccia){
memset(memo,-1,sizeof memo);
return dp(0,N);
}
/*int main() {
#ifdef EVAL
freopen("input.txt","r",stdin);
freopen("output.txt","r",stdout);
#endif
scanf("%d",&N);
for(int i=0;i<N;i++)
scanf("%d",freccia+i);
//memset(memo, -1, sizeof memo);
printf("%d",Gira(N, freccia));
return 0;
}*/
( http://pastebin.com/BdCUwjnP )
Vedete Bug?
