poj 3378 Crazy Thairs dp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
typedef unsigned long long ll;
using namespace std;
const int maxn=5e4+9;
ll tree[6][maxn],dp[maxn][6];
int a[maxn];
int n;
typedef struct node
{
int data,id;
bool operator <(const node &xx) const
{
if(data==xx.data)
return(id<xx.id);
return(data<xx.data);
}
};
int lowbit(int x)
{
return(x&-x);
}
void insert(int x,int t,ll tmp)
{
for(int i=x;i<=n;i+=lowbit(i))
tree[t][i]+=tmp;
}
ll getsum(int x,int t)
{
ll ans=0;
for(int i=x;i>=1;i-=lowbit(i))
ans+=tree[t][i];
return(ans);
}
int main()
{
set <node> d;
// freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF)
{
d.clear();
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
node x;
x.data=a[i];
x.id=i;
d.insert(x);
}
int k=0,tmp;
for(set <node>::iterator i=d.begin();i!=d.end();i++)
{
if(i==d.begin()||i->data!=tmp) k++;
a[i->id]=k;
tmp=i->data;
}
memset(dp,0,sizeof(dp));
memset(tree,0,sizeof(tree));
for(int i=1;i<=n;i++)
{
dp[i][1]=1;
insert(a[i],1,dp[i][1]);
for(int j=1;j<=4;j++)
{
dp[i][j+1]=getsum(a[i]-1,j);
insert(a[i],j+1,dp[i][j+1]);
}
}
ll ans=0,ans1=0;
for(int i=1;i<=n;i++)
{
ans+=dp[i][5];
ans1+=ans/ll(1000000000000000);
ans%=1000000000000000;
}
if(ans1)
{
printf("%lld",ans1);
printf("%015lld
",ans);
}
else
printf("%lld
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.