思路：
得益于幾星期前琢磨的sort的cmp用法印蔗，做這題的時(shí)候也用到了貪心思想乾翔，整一個(gè)結(jié)構(gòu)體數(shù)組，先按半徑從大到小進(jìn)行排序河劝。數(shù)組v初始都為0表示都可以種在一起，這里的v[i]=0的含義是第i棵可以跟上一棵樹種在一起矛紫，不能則設(shè)v[i]=1赎瞎。所以首先默認(rèn)先種下半徑最大的那棵樹，再往下尋找跟他不相交的樹颊咬，如果相交則該樹的數(shù)組v值為1务甥，后面再根據(jù)數(shù)組v（值為0）的條件種下第二棵，再相對(duì)這種下的第二棵樹尋找與他不相交的（ps：此時(shí)的不相交真正的含義為與第一第二棵都不能相交）.....后面以此類推喳篇，便可求出最大種植面積敞临。
源代碼：
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct tree{
int x,y,r;
}a[1000];
bool cmp(tree a,tree b){
return a.r>b.r;
}
double dist(int x1,int y1,int x2,int y2){
return sqrt((x1-x2)*(x1-x2)-(y1-y2)*(y1-y2));
}
int main(){
int n,v[1000];
double d;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i].x>>a[i].y>>a[i].r;
v[i]=0;//默認(rèn)都可以種在一起
}
sort(a,a+n,cmp);
int s=0;
for(int i=0;i<n;i++){
if(!v[i]){
s+=a[i].r*a[i].r;
for(int j=0;j<n;j++){
d=dist(a[i].x,a[i].y,a[j].x,a[j].y);
if(d<a[i].r+a[j].r){//相交，j不能和i仲在一齊
v[j]=1;
}
}
}
}
cout<<s<<endl;
}
分析：
原本想這個(gè)用回溯那太簡單了麸澜。挺尿。。可是我不會(huì)编矾。熟史。。后來聽說會(huì)超時(shí)就徹底放棄了窄俏。后面復(fù)盤的時(shí)候?qū)@題還是不甘心以故，雖然作業(yè)是抄的但是也終于是明白了這里為什么可以用dp做。
設(shè)兩個(gè)數(shù)組a裆操，b，數(shù)組a表示單數(shù)項(xiàng)炉媒，b數(shù)組代表雙數(shù)項(xiàng)踪区，均為動(dòng)態(tài)數(shù)組。初始設(shè)a數(shù)組里的數(shù)據(jù)均是1吊骤，表示第一列取到的1缎岗，2，3白粉，4的可能都是1传泊，b數(shù)組先不管默認(rèn)都為0。然后利用數(shù)組a開始計(jì)算第二項(xiàng)的可能性鸭巴，因?yàn)椤芭紨?shù)項(xiàng)都比前一項(xiàng)小”眷细，所以從n開始累加sum，且數(shù)組b最大項(xiàng)只能取到n-1鹃祖，初始默認(rèn)sum=a[n]（為當(dāng)前b[n-1]的所有可能性）溪椎，則在給出的測試用例n=4情況下，b[3]=a[4]=1(當(dāng)?shù)诙?xiàng)為3時(shí)恬口，前一項(xiàng)可能性一定只有只有1個(gè)為4）校读，而b[2]則是有兩個(gè)則為a[3]+a[4] (sum=a[4]-->sum+=a[3]).....以此類推可得出第二項(xiàng)的數(shù)組b，相同的方法利用數(shù)組b計(jì)算新單數(shù)項(xiàng)的數(shù)組a（3）.....直到算完最后一項(xiàng)的所有可能性祖能，判斷輸入的m的奇偶性歉秫，再相應(yīng)地對(duì)數(shù)組a或者數(shù)組b中的數(shù)據(jù)進(jìn)行逐一累加，得出來的總數(shù)即為所求擺動(dòng)序列所有可能性的個(gè)數(shù)养铸。
源代碼：
#include<iostream>
using namespace std;
int m, n;
int main() {
long long ans = 0;
cin >> m >> n;
long long a[1001], b[1001];
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for(int i = 1; i <= n; i++) a[i] = 1;
a[1] = 0;
for(int i = 2; i <= m; i++) {
if(i%2) {
long long sum = b[1];
for(int j = 2; j <= n; j++) {
a[j] = sum % 10000;
sum = (sum + b[j]) % 10000;
}
} else {
long long sum = a[n];
for(int j = n - 1; j >= 1; j--) {
b[j] = sum % 10000;
sum = (sum + a[j]) % 10000;
}
}
}
if(m%2) {
for(int i = 1; i <= n; i++)
ans = (ans + a[i]) % 10000;
}
else {
for(int i = 1; i <= n; i++)
ans = (ans + b[i]) % 10000;
}
cout<<ans<<endl;
}
