问题 G: 保卫羊村

问题 G: 保卫羊村

题目描述

伟大的Yyz帮助羊羊们逃出了城堡，可Jack自然不会善罢甘休。“我会诅咒你们的！”杰杰恼羞成怒地喊道。回到羊村后，羊羊们发现羊村地震了。看来Jack的诅咒生效了。当务之急是修补因地震而坍塌的围墙。
围墙上有n个圆形洞。第i个洞的直径是di米，修复第i个洞的时间是ti分钟。不妙的是，据可靠情报，灰太狼在c分钟后就将袭击羊村，你的任务当然是使灰太狼来时剩余洞的总面积最小，以便羊羊们在灰太狼来时能够更好的防御。

输入

第1行，一个正整数n，表示洞的总数。
第2~n+1行，每行有2个正整数di和ti（di，ni≤10,000），di表示第i个洞的直径，ti表示修复第i个洞的时间。
第n+2行，一个正整数c（c≤1,000,000），表示灰太狼将在c分钟后到来。
输出
输出一行一个实数s，表示灰太狼来时剩余洞的最小面积。
π取3.1416，最后结果保留4位小数。

样例输入 Copy

4
4 1
6 2
12 3
7 2
6

样例输出 Copy

28.2744

提示

80%的数据满足：1≤n≤15；
100%的数据满足：1≤n≤100。

思路

01背包问题，dp记得开大一些，因为时间ci比较大。

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const double pi=3.1416;
struct vode
{int ti;double di;
}ai[120];
double dp[1000100],area[120];
double find_area(double r)
{return r*r*pi;
}
int main()
{int n,ci;double sum=0;cin>>n;for(int i=1;i<=n;i++){cin>>ai[i].di>>ai[i].ti;area[i]=find_area(ai[i].di/2.0);sum+=area[i];}cin>>ci;for(int i=1;i<=n;i++){for(int j=ci;j>=ai[i].ti;j--){dp[j]=max(dp[j],dp[j-ai[i].ti]+area[i]);}}cout<<fixed<<setprecision(4)<<sum-dp[ci];return 0;
}