首页 > 代码库 > UVa 10970 大块巧克力
UVa 10970 大块巧克力
https://vjudge.net/problem/UVA-10970
题意：
把一个m行n列的矩形巧克力切成mn个1×1的方块，需要切几刀。
思路：
可以考虑用动态规划的方法去做，当然，最简单的是直接找到规律，直接计算出来。
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<cstring> 5 using namespace std; 6 7 int n, m; 8 int d[305][305]; 9 10 int dp(int i, int j)11 {12 int& ans = d[i][j];13 if (ans != -1) return ans;14 if (i == 1) return ans=j - 1;15 if (j == 1) return ans=i - 1;16 if (i % 2 == 0) ans = 2 * dp(i / 2, j) + 1;17 else if (j % 2 == 0) ans = 2 * dp(i, j / 2) + 1;18 else return ans = dp(i - 1, j) + j;19 }20 21 int main()22 {23 ios::sync_with_stdio(false);24 //freopen("D:\\txt.txt", "r", stdin);25 while (cin >> n >> m)26 {27 memset(d, -1, sizeof(d));28 dp(n, m);29 cout << d[n][m] << endl;30 }31 }
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<cstring> 5 using namespace std; 6 7 int n, m; 8 9 int main()10 {11 ios::sync_with_stdio(false);12 //freopen("D:\\txt.txt", "r", stdin);13 while (cin >> n >> m)14 {15 cout << m*n - 1 << endl;16 }17 }
UVa 10970 大块巧克力
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。