给出一个地图,每个点上有相应数量的cheese,从(0,0)开始,每到一个格子就把这个格子里的cheese吃光,每走一步方向只能是上下左右,每一步最多的格子数为k,每一步之后的一格所包含的cheese数量要比之前一格多…怎样才能使得所得的cheese数最多呢,输出最多的cheese数.
刚开始我想的搜索,但是无门.但是看题之前已经知道是dp了,就一直往那方面想,一开始就想到了从cheese最大点开始,把他相应范围内的最大数更新一下,也就是dp[i][j] = map[i][j] + (与i,j在合法范围内dp[*][*]最大值),dp[i][j]表示从(i,j)开始所能得到的最多cheese。但是想想实现起来比较麻烦。昨天晚上睡觉上微博的时候,突然想到把这些点按照cheese数排列,然后从前往后进行dp,相当于LIS,只不过中间的限制条件比较多。按照这个思路,我写出代码,并且ac掉:
Accepted | 1107 | C++ | 2060 | 188 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> using namespace std; #define MAX 100 struct node { int x; int y; int a;//cheese数量 }temp; int cmp(const void * a,const void *b ) { int aa = ( (struct node*)a )->a; int bb = ( (struct node*)b )->a; return bb-aa; } int ok(node *a,int i,int j,int k) { if( a[i].x==a[j].x && (a[i].y-a[j].y <= k &&a[i].y-a[j].y >= -k ) ) return 1; if( a[i].y==a[j].y && (a[i].x-a[j].x <= k &&a[i].x-a[j].x >= -k ) ) return 1; return 0; } int main(void) { node map[MAX*MAX + 10]; int dp[MAX*MAX + 10]; int i,j,count,k,n,biao,max; while( cin >> n >> k ) { if( n == -1 && k == -1 ) break; count = n*n; for( i = 0; i < n; i++ ) for( j = 0; j < n; j++ ) { cin >> map[i*n+j].a; map[i*n+j].x = i; map[i*n+j].y = j; } qsort( map,count,sizeof(node),cmp ); dp[0] = map[0].a; for( i = 1; i < count; i++ ) { max = 0; for( j = 0; j < i; j++ ) if( map[j].a > map[i].a && ok(map,i,j,k) && dp[j] > max ) max = dp[j]; dp[i] = max + map[i].a; } for( i=0; i <count; i++ ) if( map[i].x == 0 && map[i].y == 0) {cout<<dp[i]<<endl;break;} } return 0; }
但是呢,cheese数比(0,0)小的点对于结果没有影响,所以可以把这些点去掉,再来一次:
时间减半:
Accepted | 1107 | C++ | 930 | 188 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> using namespace std; #define MAX 100 struct node { int x; int y; int a;//cheese数量 }temp; int cmp(const void * a,const void *b ) { int aa = ( (struct node*)a )->a; int bb = ( (struct node*)b )->a; return bb-aa; } int ok(node *a,int i,int j,int k) { if( a[i].x==a[j].x && (a[i].y-a[j].y <= k &&a[i].y-a[j].y >= -k ) ) return 1; if( a[i].y==a[j].y && (a[i].x-a[j].x <= k &&a[i].x-a[j].x >= -k ) ) return 1; return 0; } int main(void) { node map[MAX*MAX + 10]; int dp[MAX*MAX + 10]; int i,j,count,k,n,biao,max; while( cin >> n >> k ) { if( n == -1 && k == -1 ) break; count = 0; cin >> temp.a ; temp.x = 0;temp.y = 0; biao = temp.a; map[ count++ ] = temp; for( i = 0; i < n; i++ ) for( j = (i==0?1:0); j < n; j++ ) { cin >> temp.a; if( temp.a <= biao ) continue; temp.x = i;temp.y = j; map[ count++ ] = temp; } qsort( map,count,sizeof(node),cmp ); for( i = 0; i < count; i++ ) dp[i] = map[i].a; for( i = 1; i < count; i++ ) { max = 0; for( j = 0; j < i; j++ ) if( ok(map,i,j,k) && dp[j] > max && map[i].a < map[j].a) max = dp[j]; dp[i] += max; } cout << dp[count-1] << endl; } return 0; }
然后我看了看status版,发现我的效率非常低,别人的都是100ms以下的,我想了想,能影响一个点值的因素只有他上下左右距离k以内的点,所以再建立一个图保存cheese值,ac之后发现有了大大的提高,时间剪了不少:
Accepted | 1107 | C++ | 100 | 188 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #define MAX 100 using namespace std; struct node { int x; int y; int a;//cheese数量 }temp; int cmp(const void * a,const void *b ) { return ( (struct node*)b )->a - ( (struct node*)a )->a; } int main(void) { node map[MAX*MAX + 10]; int dp[MAX+10][MAX+10]; int mat[MAX+10][MAX+10]; int i,j,m,count,k,n,biao,max; int xx,yy; int dir[4][2] = {1,0,0,1,0,-1,-1,0}; while( cin >> n >> k ) { if( n == -1 && k == -1 ) break; count = n*n; for( i = 0; i < n; i++ ) for( j = 0; j < n; j++ ) { cin >> map[i*n+j].a; map[i*n+j].x = i; map[i*n+j].y = j; dp[i][j] = map[i*n+j].a; mat[i][j] = dp[i][j]; } qsort( map,count,sizeof(node),cmp ); for( i = 0; i < count; i++ ) { max = 0; for( j = 0; j < 4; j++ )//四个方向 { xx = map[i].x; yy = map[i].y; for( m = 1; m <= k; m++ ) { xx += dir[j][0]; yy += dir[j][1]; if( xx >= 0 && xx < n && yy >= 0 && yy < n && mat[xx][yy] > map[i].a && dp[ xx ][ yy ] > max ) max = dp[ xx ][ yy ] ; if(!( xx >= 0 && xx < n && yy >= 0 && yy < n )) break; } } dp[ map[i].x ][ map[i].y ] += max; } cout << dp[0][0] << endl; } return 0; }
经过这三个ac之后我非常高兴,改称c语言之后80ms过了。之前我认为dp是一座大山,现在感觉慢慢开窍了,以后要做做这类题,感觉很有成就感,继续加油喽~
你有意见啊?
= =..我记得我在上个题里留的言。。怎么跑这题里了 = =。。