Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 5 KB
using System;
using System.IO;
using System.Text;
using System.Collections;
namespace Stone
{
class Program
{
private int[] orig;
private ArrayList halmaz;
private int[,,,] dp;
private ArrayList doHalmaz( string prefix ) {
ArrayList tmp = new ArrayList();
for( int i = 0; i<prefix.Length; i++ ) {
if( !tmp.Contains( prefix[i] ) ) {
tmp.Add( prefix[i] );
}
}
return tmp;
}
private int opt( string prefix, int idx ) {
int o1;
int o2;
bool oki;
halmaz = doHalmaz( prefix );
if( idx == orig.Length ) return orig.Length-prefix.Length;
if( prefix.Length == 0 ) {
oki = true;
} else if(prefix[prefix.Length-1] == orig[idx]) {
oki = true;
} else oki = false;
if( !halmaz.Contains( orig[idx] ) || oki ) {
if( !halmaz.Contains( orig[idx] ) ) {
halmaz.Add( orig[idx] );
}
o1 = opt(prefix+orig[idx], idx+1);
} else o1 = Int32.MaxValue;
o2 = opt(prefix, idx+1);
return (o1>o2)?o2:o1;
}
private int opt( Prefix prefix ) {
int o1;
int o2;
bool oki;
if( dp[prefix.prefix[0], prefix.prefix[1], prefix.prefix[2], prefix.prefix[3]] > -1 ) {
return dp[prefix.prefix[0], prefix.prefix[1], prefix.prefix[2], prefix.prefix[3]];
}
if( prefix.Index == orig.Length ) return orig.Length-prefix.Length;
if( prefix.Length == 0 ) {
oki = true;
} else if(prefix.Last == orig[ prefix.Index ]) {
oki = true;
} else oki = false;
int halmaz_save = prefix.prefix[0];
if( !prefix.HalmazEleme( orig[ prefix.Index ] ) || oki ) {
if( !prefix.HalmazEleme( orig[ prefix.Index ] ) ) {
prefix.HalmazAdd( orig[ prefix.Index ] );
}
o1 = opt( new Prefix( prefix.prefix[0], orig[ prefix.Index ], prefix.Length+1, prefix.Index+1 ) );
} else o1 = Int32.MaxValue;
o2 = opt( new Prefix( halmaz_save, prefix.Last, prefix.Length, prefix.Index+1 ) );
dp[prefix.prefix[0], prefix.prefix[1], prefix.prefix[2], prefix.prefix[3]] = (o1>o2)?o2:o1;
return (o1>o2)?o2:o1;
}
private string Join( string[] array ) {
StringBuilder sb = new StringBuilder();
for( int i=0; i<array.Length; i++ ) {
if( array[i] != "" ) {
sb.Append( array[i] );
}
}
return sb.ToString();
}
public void DoIT() {
StreamReader SR;
SR = File.OpenText(@"..\..\stones\stones.in");
string s1 = String.Empty;
string s2 = String.Empty;
while( true ) {
s1 = SR.ReadLine();
if( s1 == "0 0" ) break;
s2 = SR.ReadLine();
string[] tmp = s2.Split(' ');
dp = new int[32,6,101,101];
for( int a=0; a<32; a++ ) {
for( int b=0; b<6; b++ ) {
for( int c=0; c<101; c++ ) {
for( int d=0; d<101; d++ ) {
dp[a,b,c,d] = -1;
}
}
}
}
orig = new int[ tmp.Length ];
for( int i=0; i<tmp.Length; i++ ) {
orig[i] = Int32.Parse( tmp[i] );
}
Console.WriteLine( opt( new Prefix() ) );
}
}
public static void Main(string[] args)
{
Program prg = new Program();
prg.DoIT();
Console.WriteLine("--end--");
Console.ReadKey(true);
}
}
}
using System;
namespace Stone
{
public class Prefix
{
public int[] prefix;
public int Length {
get{
return prefix[2];
}
set{
prefix[2] = value;
}
}
public int Last {
get{
return prefix[1];
}
set{
prefix[1] = value;
}
}
public int Index {
get{
return prefix[3];
}
set {
prefix[3] = value;
}
}
private int pow2( int c ) {
int res = 1;
for( int i=0; i<c; i++ ) {
res *= 2;
}
return res;
}
public bool HalmazEleme( int c ) {
if( (prefix[0] & pow2( c-1 ) ) != 0 ) {
return true;
}
return false;
}
public void HalmazAdd( int c ) {
prefix[0] = prefix[0] | pow2( c-1 );
}
public Prefix( )
{
prefix = new int[4];
prefix[0] = 0;
prefix[1] = 0;
prefix[2] = 0;
prefix[3] = 0;
}
public Prefix( int a, int b, int c, int d ) {
prefix = new int[4];
prefix[0] = a;
prefix[1] = b;
prefix[2] = c;
prefix[3] = d;
}
public string proba() {
return prefix[0] + " " + prefix[1] + " " + prefix[2] + " " + prefix[3];
}
}
}
