本文共 3361 字,大约阅读时间需要 11 分钟。
1、
2、题目大意:
给出n个矩形并排,给出他们的高度,求可以在此基础上找出一个面积最大且底边在基线上的矩形,输出最大面积
一开始用的区间DP,样例都过了,但发现dp[N][N]超内存了,看网上代码,居然是用结构体或两个一维数组表示的
3、题目:
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 13118 | Accepted: 4238 |
Description
Input
Output
Sample Input
7 2 1 4 5 1 3 34 1000 1000 1000 10000
Sample Output
84000
Hint
Source
#include区间DP做的,超内存的代码:#include #include #include #include using namespace std;#define ll long long#define N 100005struct node{ ll num; ll left; ll right;} a[N];int main(){ int n; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(int i=1; i<=n; i++) { scanf("%lld",&a[i].num); a[i].left=i; a[i].right=i; } a[0].num=-1; a[n+1].num=-1; for(int i=1; i<=n; i++) { while(a[i].num<=a[a[i].left-1].num) a[i].left=a[a[i].left-1].left; } for(int i=n; i>=1; i--) { while(a[i].num<=a[a[i].right+1].num) a[i].right=a[a[i].right+1].right; } ll tmp=-1; for(int i=1; i<=n; i++) { if(a[i].num*(a[i].right-a[i].left+1)>tmp) tmp=a[i].num*(a[i].right-a[i].left+1); } printf("%lld\n",tmp); } return 0;}
#include#include #include #include #include using namespace std;#define N 100005#define INF 1000000005int a[N];int dp[22005][22005];int main(){ int n; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); dp[i][i]=a[i]; } for(int i=2;i<=n;i++) { for(int j=1;j+i-1<=n;j++) { int s=j; int e=j+i-1; int minn=INF; for(int k=s;k<=e;k++) { if(a[k]
转载地址:http://xgddi.baihongyu.com/