本文主要是介绍POJ 1009不算解题报告的解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
好久没有写poj的题了，一定要坚持下来。毕竟是要写写代码为生的，算法的重要性不言而喻。1009这道题已经纠结了很久了，其实题目不难，看到后思路也很直观，就是考虑到同一个数字跨过三行以上时，中间部分肯定就可以不用计算，直接为零。之前觉得可以建立一个map，当包括中间值在内的9个数组成的数组之前已经算过的话，直接输出map的value就可以了。不过似乎这样每次搜寻、比较，效率反而低了。另外，写的时候想着如果输入的数据比较多，它们的个数之和可能会超过int范围，看来是我多想了。
这道题总算硬着头皮“看”完了。自己尝试了几遍都没有完成，最后还是看了大牛的解题报告。所以其实自己也没有写完。在这里总结一下，希望有提高。
写程序的时候按照框架写，先想好要分几部分，然后再扩充每部分的细节内容。这道不难的题，我一开始就被细节部分弄的一点信心也没有了。
这是大牛的代码。这里加了一点注释。源代码可以参见http://xay0.blog.163.com/blog/static/43925338200801202220646/
c++ code:
| thestoryofsnow | 1009 | Accepted | 228K | 16MS | C++ | 4691B |
#include <stdio.h>
#include <assert.h>int n, t, k;
int num[2000], sum[2000], digit[2000], ansdigit[5000], ansnum[5000];
//求绝对值函数，可以用math中的同名函数
int abs(int x)
{if (x < 0) return -x;return x;
}
//循环变量i和周围元素位置映射
/*****
*0 1 2
*3 4
*5 6 7
******/
inline int map(int c, int now)
{switch (c){case 0: return now - t - 1;case 1: return now - t;case 2: return now - t + 1;case 3: return now - 1;case 4: return now + 1;case 5: return now + t - 1;case 6: return now + t;case 7: return now + t + 1;}assert(false);return -1;
}
//算出位置y的元素值,这里forward很巧妙，为0向前找，为1向后找
int number(int c, int y, bool forward)
{int i;if (forward){for (i = c; i <= n; ++i)if (sum[i] >= y) break;return i;}else{for (i = c; i > 0; --i)if (sum[i] < y) break;return i+1;}
}
//判断边界情况
bool ok(int now, int i)
{if (now < t && (i == 1 || i == 0 || i == 2)) return false;//起始行的前一行if (now > sum[n] - t && (i == 6 || i == 5 || i == 7)) return false;//结束行的后一行if (now % t == 1 && (i == 0 || i == 3 || i == 5)) return false;//左边一行的左边if (now % t == 0 && (i == 2 || i == 4 || i == 7)) return false;//右边一行的右边return true;
}
//比较与周围8个元素之差的绝对值大小
int get(int x, int now)
{int i, max = 0, m;for (i = 0; i < 8; ++i){m = map(i, now);if (ok(now, i) && m > 0 && m <= sum[n]){m = number(x, m, i / 4);if (max < abs(digit[x] - digit[m])) max = abs(digit[x] - digit[m]);}}return max;
}
//减少重复计算
int late(int x, int now, int r)
{int p;if (r <= now) return 1;if (now % t != 1){if (digit[number(x, now - 1, 0)] != digit[x]) return 1;if (now > t){p = number(x, now - t - 1, 0);if ((sum[p] - 1) / t < (now - 1) / t){if (sum[p] <= now - t + 1) return 1;if (r > sum[p] - 1 + t) r = sum[p] - 1 + t;}}if (now <= sum[n] - t){p = number(x, now + t - 1, 1);if ((sum[p] - 1) / t == (now - 1) / t + 1){if (sum[p] <= now + t + 1) return 1;if (r > sum[p] - 1 - t) r = sum[p] - 1 - t;}}return r - now + 1;}else{if (now > t){p = number(x, now - t, 0);if ((sum[p] - 1) / t < (now - 1) / t){if (sum[p] <= now - t + 1) return 1;if (r > sum[p] - 1 + t) r = sum[p] - 1 + t;}}if (now <= sum[n] - t){p = number(x, now + t, 1);if ((sum[p] - 1) / t == (now - 1) / t + 1){if (sum[p] <= now + t + 1) return 1;if (r > sum[p] - 1 - t) r = sum[p] - 1 - t;}}return r - now + 1;}
}
//程序的主体部分，计算start和end之间的部分。这段程序实际上是个递归，多行的情况可以归约到start和end在同一行的情况
void make(int x, int start, int end)
{int i, r;int a = (start - 1) / t, b = (end - 1) / t;if (a != b)//如果不在同一行{make(x, start, b * t);//归约make(x, b * t + 1, end);//同一行的情况return;}//通过get函数算出最大的绝对值，保存在last中，the保存当前位置算出的最大绝对值。如果两者相同，就要进行合并int last = get(x, start), sum = 0, the;for (i = start; i <= end;){the = get(x, i);r = late(x, i, end - 1);if (the == last)sum += r;//合并else{ansdigit[++k] = last;ansnum[k] = sum;sum = r;last = the;}i += r;}ansdigit[++k] = last;ansnum[k] = sum;
}
int main()
{int i, x, y;sum[0] = 0;while (scanf("%d", &t) && t){i = 0;k = 0;while (scanf("%d%d", &x, &y) && (x || y)){digit[++i] = x; //digit数组保存输入元素num[i] = y;//num数组保存元素个数sum[i] = sum[i - 1] + num[i];//sum数组记录元素个数和，主要用于判断元素i的周围8个元素是什么}n = i;for (i = 1; i <= n; ++i){if (num[i] <= t + t + 2)//不存在同一个元素跨越3行的情况make(i, sum[i - 1] + 1, sum[i]);else{make(i, sum[i - 1] + 1, sum[i - 1] + t + 1);//前面部分同if部分ansdigit[++k] = 0;//中间直接为0ansnum[k] = num[i] - 2 * t - 2;//0的个数make(i, sum[i] - t, sum[i]);//后面部分也需要计算}}printf("%d\n", t);//输出开始for (i = 1; i <= k;){int outdigit = ansdigit[i];int outnum = 0;while (i <= k && ansdigit[i] == outdigit)//如果相邻元素相同，需要合并outnum += ansnum[i++];printf("%d %d\n", outdigit, outnum);}printf("0 0\n");}printf("0\n");
}这篇关于POJ 1009不算解题报告的解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
