题目描述

此处

思路

DP题，有两种思路

1. Fi 表示前i个圆，在总长不超过j的范围内的最大面积，排序得按照圆的右边界排序
2. F[i]表示前i个圆，且第i个为最后一个放置时能达到的最大面积，排序按照圆心位置排序

代码

思路一

#include <bits/stdc++.h>
using namespace std;

struct node{
    int x,r;
}a[1005];

bool cmp(node x,node y){
    return x.x+x.r<y.x+y.r;
}

int n,f[1005][1005],ans,mt;

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&a[i].x);
    for (int i=1;i<=n;++i) scanf("%d",&a[i].r),mt=max(mt,a[i].x+a[i].r);
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;++i){
        for (int j=1;j<=mt;++j){
            if (j>=a[i].x+a[i].r){
                f[i][j]=max(f[i-1][a[i].x-a[i].r]+a[i].r*a[i].r,f[i-1][j]);
            }else{
                f[i][j]=f[i-1][j];
            }
            ans=max(ans,f[i][j]);
        }
    }
    printf("%.0lf\n",ans*3.1415926); //转化成面积
    return 0;
}

思路二

#include<bits/stdc++.h>
#define sr(x) ((x)*(x)) //平方函数宏定义
using namespace std;
struct node{
    int x,r;
}p[1005];
int n,f[1005];
bool cmp(node a,node b){
    return a.x<b.x;
}
int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&p[i].x);
    for(int i=1; i<=n; i++) scanf("%d",&p[i].r);
    sort(p+1,p+1+n,cmp);
    int res=0;
    for(int i=1; i<=n; i++){
        f[i]=sr(p[i].r);
        for(int j=1; j<i; j++){
            if(p[j].r+p[i].r<=p[i].x-p[j].x){
            //判断 j 和 i 是否冲突，不冲突可以转移
                f[i]=max(f[i],f[j]+sr(p[i].r));
            }
        }
        res=max(res, f[i]); //注意答案不一定是最后一个
    }
    printf("%.0f\n",3.1415926*res);
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/72/