感觉自己还是做题不够，临场的时候很难想到很好的办法。
结束之后和朋友讨论了一下，很快思路就变得清晰了，其实就是很简单的两道题。
第一题我用了两个循环，时间复杂度太高了；
第二题是个动态规划，当时没想到好的方法，后来抽象成了01背包问题就感觉很简单了。
新写的代码不知道是不是完全对的，仅供参考吧。
第一题：
题干很长，但是抽象一下其实就是，求每个数组元素后距离其最近的比他大的数与他的距离，有则输出距离，无则输出0；
我用了一个堆栈存，用结构体记录数据和他的编号，感觉还是算两个循坏吧，不知道是不是准确的解法，欢迎指正。
#include <iostream>
#include<stack>
#include<vector>
using namespace std;
struct pNum {
int p;
int num;
};
int main()
{
stack<pNum> price;
int n;
cin >> n;
vector<int> res;
for (int i = 0; i < n; i++)
{
res.push_back(0);
}
for (int i = 0; i < n; i++)
{
int m;
cin >> m;
while (!price.empty())//循环直到栈为空或者遇到比当前输入大的数字。
{
if (m > price.top().p)
{
res[price.top().num] = i - price.top().num; //比栈顶的数字大则计算距离并出栈
price.pop();
}
else
{
break;
}
}
pNum a;
a.num = i;
a.p = m;
price.push(a);
}
for (int i = 0; i < n; i++)
{
cout << res[i] << endl;
}
return 0;
}
第二题：
题目大概意思是，有一堆绳子，把这堆绳子分成两份，求这两份绳子能组成的最大的长方形的面积。
这个题目一看就是动态规划了，但是刚开始真的没有什么好的思路，就只是想着，要想等周长面积最大，那肯定就是越接近正方形了，就是线能组成越接近周长一半。
后来同学说了一句感觉有点向简化的背包问题，然后豁然开朗想到一个肯定能解决的方法，但是感觉空间复杂度是很高的。
大概就是建立一个容量为总长一半的背包，然后找能装的最多的就好了。
但是就是由于空间用得太多了，就觉得这个方法可能还是错的。。。
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> li;
int al = 0;
for (int i = 0; i < n; i++)
{
int l;
cin >> l;
al += l;
li.push_back(l);
}
vector<vector<int>> dp;
vector<int> d;
int hal = al / 2;
for (int j = 0; j < hal+1; j++)//就是这里，感觉空间用的太多了，感觉这里可能就过不了了
{
d.push_back(0);
}
for (int i = 0; i < n+1; i++)
{
dp.push_back(d);
}
for (int i = 1; i < n+1; i++)
{
for (int j = 1; j < hal+1; j++)
{
if (li[i - 1] > j)
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - li[i - 1]]+li[i-1]);
}
}
}
cout << (al - dp[n][hal])*dp[n][hal];
return 0;
}
全部评论
(2) 回帖