校赛题目
A best fit ring 线段树+DP
给一些点的坐标和点的值，同环的分数要加和，然后询问时要求给出最大值的范围，也就是连续环值最大（最大连续子段和），询问的过程中会有点的值的更改。
code：
#include <cstdio>#include <cstring>int count(int h, int w, char g[][21]){ int cnt = 0; int i , j; for ( i = 0; i < h; ++i ) for ( j = 0; j < w; ++j ) if ( g[i][j] != '.' ) cnt++; return cnt; }void dis(int h, int w, char g[][21], int i, int j ){ int fang[4][2] = {{0,1},{0,-1}, {1,0},{-1,0}}; int ii, x, y, c; int tag[27]; int que[27][2]; for ( ii = 0; ii < 27; ++ii) tag[ii] = 0; for ( ii = 0; ii < 4; ii++) { x = i + fang[ii][0]; y = j + fang[ii][1]; while ( x >= 0 && x < h && y >=0 && y < w ) { if ( g[x][y] != '.' ) { c = g[x][y] -'A'; if ( tag[c] ) { g[x][y] = '.'; g[que[c][0]][que[c][1]] = '.'; } else { tag[c] = 1; que[c][0] = x; que[c][1] = y; } break; } x += fang[ii][0]; y += fang[ii][1]; } } }void solve(int h, int w, char g[][21]){ int cnt = count(h,w,g); char gg[21][21]; int i , j; for ( i = 0; i < h; ++i ) strcpy(gg[i],g[i]); for ( i = 0; i < h; ++i ) for ( j = 0; j < w; ++j ) if ( g[i][j] == '.' ) dis(h, w, gg, i, j); for ( i = 0; i < h; ++i ) strcpy(g[i],gg[i]); if ( cnt == count(h,w,g) ) return ; solve(h,w,g);}int main(){ char g[21][21]; int n; int i; int h, w; while (scanf("%d%d", &h, &w) != EOF && h + w) { for ( i = 0; i < h; ++i ) scanf("%s", g[i]); solve(h,w,g); printf("%d\n",count(h,w,g)); } return 0;}??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?