FZU2129 DP 본질이 다른 하위 시퀀스

625 단어 동적 기획
#include
#include
#include
using namespace std;
typedef long long ll;
const ll N=1e6+10,M=1e9+7;
ll A[N],B[N],DP[N];
int main(){
    int n;
    while(cin>>n){
        memset(DP,0,sizeof DP);
        memset(A,0,sizeof A);
        memset(B,0,sizeof B);
        for(int i=1;i<=n;++i)scanf("%lld",&A[i]);
        for(int i=1;i<=n;++i){
            if(B[A[i]]==0)DP[i]=DP[i-1]*2+1;
            else DP[i]=DP[i-1]*2-DP[B[A[i]]-1]+2*M;
            B[A[i]]=i;
            DP[i]%=M;
        }
        cout<

좋은 웹페이지 즐겨찾기