Main » 2012 » October » 30 » [Tyvj Aug11] 黄金矿工
1:18 PM [Tyvj Aug11] 黄金矿工 | |
| 描述 Description 黄金矿工是一个经典的小游戏，它可以锻炼人的反应能力。该游戏中，可以通过"挖矿”获得积分并不断升级。玩家可以在线玩flash版黄金矿工，也可以下载后玩单机版黄金矿工。目前，黄金矿工小游戏有多个版本，例如黄金矿工双人版，黄金矿工单人版等。 Jimmy是一位黄金矿工，他所在的金矿是一个n*n的矩形区域（俯视），区域内有黄金、石头和TNT，由一个n*n的矩阵描述。黄金的价值对应矩阵中的正值，石头的价值对应矩阵中的负值，TNT由0表示。换句话说，挖到黄金赚钱，石头亏损，如果挖到TNT就挂了~_~ Jimmy租到的挖矿工具很特别，它的形状是一个长宽任意（均为正整数）的矩形，可以取走被该工具覆盖的矩形区域内的所有物品，但如果该区域内有TNT，该工具将被炸毁，此时Jimmy将不得不赔偿矿主+∞元！！！需要注意的是，该工具只能在金矿范围内使用（即不得超出金矿边界），且租金为每次使用十元。 现在，Jimmy想知道，如果他至多只有一次租用该工具的机会，他能获得的最大收益是多少。当然，如果Jimmy租用该工具无论如何都会亏损，他可以不租用，此时收益为0. 输入格式 Input Format 第一行：一个整数n 接下来n行，每行n个整数（绝对值<100），为题目中所描述的矩阵。 输出格式 Output Format 一个数，即Jimmy所能获得的最大收益。 样例输入 Sample Input 3 0 -1 -1 0 -12 0 -19 0 0 样例输出 Sample Output 0 数据范围和注释 Hint 无论Jimmy怎么挖矿，挖到的不是石头，就是TNT，总之无论如何都会亏损，所以选择不租用工具，收益为0 数据范围： 对于30%的数据：0<n<=10 对于60%的数据：0<n<=100 对于100%的数据：0<n<=300 题解： 本题是一道关于最大子矩阵和的动态规划题，也是本弱菜第一次接触，但由于网上的一篇关于最大子矩阵和的PPt，把我给坑住了。。所以，自己遇到题要好好想想，不要被一些弱爆的PPt坑掉。。。 本题的状态时q[i][j]。。i,j表示第i行到第j行这区间的最大子矩阵和。这样就可以将本题转化为区间最大和问题。。预处理w[i][j]为以i,j为端点和以（0,0）为端点的矩形的值。很好处理。。呵呵，说到这应该就简单了。。注意有一点，就是，值为0的店是TNT，不能要。多亏Yeefan Zhu的提醒，可以将该点置为负无穷。。简单易用。。 上代码： C++语言:made by PaulInsider!
#include #include #include using namespace std; long long n,w[400][400]={0},a,q[400][400]={0},answer=0,ans=0,tmp; int main() { freopen ("miner.in","r",stdin); freopen ("miner.out","w",stdout); cin>>n; for (int o=1;o<=n;o++) { for (int p=1;p<=n;p++) { cin>>a; if (a==0) a=-100000000; w[o][p]=w[o-1][p]+w[o][p-1]-w[o-1][p-1]+a; } } for (int i=1;i<=n;i++) { for (int j=i;j<=n;j++) { ans=w[j][0]-w[i-1][0]; q[i][j]=w[j][0]-w[i-1][0]; for (int k=1;k<=n;k++) { tmp=w[j][k]-w[i-1][k]; if (tmp-ans>q[i][j]) q[i][j]=tmp-ans; if (tmp<ans) ans=tmp; } if (q[i][j]>answer) answer=q[i][j]; } } if (answer<=10) cout<<0; else cout<<answer-10; return 0; } | |
|
| |
| Total comments: 0 | |