学步园

#include "stdio.h"<br /> #include "string.h"<br /> #include "windows.h"</p> <p>int partition( int * a, int * pos, int p, int r )<br /> {<br /> int x = a[p];<br /> int px = p;<br /> int i = p, j = r + 1;<br /> int temp;<br /> while ( 1 )<br /> {<br /> while ( a[++i] > x && i < r );<br /> while ( a[--j] < x );<br /> if ( i >= j )<br /> break;<br /> temp = a[i];<br /> a[i] = a[j];<br /> a[j] = temp;<br /> temp = pos[i];<br /> pos[i] = pos[j];<br /> pos[j] = temp;<br /> }<br /> a[p] = a[j];<br /> a[j] = x;<br /> pos[p] = pos[j];<br /> pos[j] = px;<br /> return j;<br /> }</p> <p>void MySort( int * a, int * pos, int p, int r )<br /> {<br /> int q;<br /> if ( p < r )<br /> {<br /> q = partition( a, pos, p, r );<br /> MySort( a, pos, p, q - 1 );<br /> MySort( a, pos, q + 1, r );<br /> }<br /> }</p> <p>long fillmark( long p, int pos ,int total )<br /> {<br /> int i;<br /> long temp = p;<br /> long mul = 1;<br /> int modt;<br /> for ( i = 0; i < total; i++ )<br /> {<br /> modt = temp % 2;<br /> if ( i > 0 )<br /> mul *= 2;<br /> if (( i + pos ) == total - 1 )<br /> {<br /> p = p + mul;<br /> break;<br /> }<br /> temp /= 2;<br /> }<br /> return p;<br /> }</p> <p>int filledmark( long p, int pos, int total )<br /> {<br /> int i;<br /> long temp = p;<br /> int modt;<br /> for ( i = 0; i < total; i++ )<br /> {<br /> modt = temp % 2;<br /> if (( i + pos ) == total - 1 && modt )<br /> return 0;<br /> temp /= 2;<br /> }<br /> return 1;<br /> }</p> <p>int myabs( int a )<br /> {<br /> if ( a >= 0 )<br /> return a;<br /> else<br /> return -a;<br /> }</p> <p>int main()<br /> {<br /> int T, i, j, k, l;<br /> char a[1001];<br /> char b[1001];<br /> int lena, lenb;<br /> int res[101] = { 0 };<br /> int map[1001] = { 0 };<br /> int temp[1001] = { 0 };<br /> int origin[1001] = { 0 };<br /> long mark[1001] = { 0 };<br /> int pos[1001] = { 0 };<br /> int max, sum;<br /> int total;<br /> scanf( "%d", &T );<br /> for ( k = 0; k < T; k++ )<br /> {<br /> sum = 0;<br /> scanf( "%s", a );<br /> scanf( "%s", b );<br /> lena = strlen( a );<br /> lenb = strlen( b );<br /> total = lena - 1;<br /> for ( j = 0; j < lena - 1; j++ )<br /> {<br /> origin[j] = myabs( a[j] - a[j + 1]);<br /> sum += origin[j];<br /> map[j] = myabs( a[j] - b[0] ) + myabs( a[j + 1] - b[0] ) - origin[j];<br /> mark[j] = fillmark( mark[j], j, total );<br /> pos[j] = j;<br /> }<br /> for ( i = 1; i < lenb; i++ )<br /> {<br /> for ( j = 0; j < lena - 1; j++ )<br /> temp[j] = myabs( a[j] - b[i] ) + myabs( a[j + 1] - b[i] ) - origin[j];<br /> MySort( temp, pos, 0, lena - 2 );<br /> for ( l = 0; l < lena - 1; l++ )<br /> {<br /> max = 0;<br /> for ( j = 0; j < lena - 1; j++ )<br /> if (filledmark( mark[l], pos[j], total ))<br /> break;<br /> mark[l] = fillmark( mark[l], pos[j], total );<br /> map[l] += temp[j];<br /> }<br /> }<br /> max = 0;<br /> for ( j = 0; j < lena - 1; j++ )<br /> if ( map[j] > max )<br /> max = map[j];<br /> res[k] = max + sum;<br /> }<br /> for ( k = 0; k < T; k++ )<br /> printf( "%d/n", res[k] );<br /> system( "pause" );<br /> return 0;<br /> }

校赛填充数字串的代码。