我的理解是问题求所有数的S=∑xi2
那么子问题求前i个区间包括 i 的 Si=∑xi2
那么运用dp的思想，但不会有状态转移方程
有如下操作
哪位大佬可以告诉我，我这种做法哪里错了呀，我觉得是对的，但是样例都过不去，代码应该没有问题检查好几遍了
小白感激不尽
#include<cstdio>
#include<set>
using namespace std;
const int maxn=1600000;
int a[maxn];
int b[maxn];
struct Node{
int l,r;
};
Node node[maxn];
set<int>s;
int main(){
int n;
set<int>::iterator it;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&node[i].l,&node[i].r);
int cnt1,cnt2;
cnt1=cnt2=1;
for(int i=node[1].l;i<=node[1].r;i++){
a[cnt1]=i*i;
s.insert(a[cnt1]);
cnt1++;
}
for(int i=2;i<=n;i++){
cnt1=1;
for(int j=node[i].l;j<=node[i].r;j++)
a[cnt1++]=j*j; //第i个区间数的和
cnt2=1;
for(int j=1;j<cnt1;j++){
for(it=s.begin();it!=s.end();it++){
b[cnt2++]=(*it)*(*it)+a[j]*a[j]; //存前i个数和的种类
}
}
s.clear(); // 清空上一次的
for(int k=1;k<cnt2;k++)
s.insert(b[k]); //去重这一次的
}
printf("%d\n",s.size());
return 0;
}
全部评论
(0) 回帖