codeforces 383D Antimatter (dp)
숫자열을 주고 문자열을 임의로 찾으면 문자열의 모든 숫자를 보기 전에'+'또는'-'를 붙여서 이 문자열의 합이 0이 되도록 하면 이런 문자열의 개수는 얼마나 됩니까?
문제 풀이:
분명히 dp이다. 데이터의 양도 크지 않다. 문제가 준 총수와 10000을 넘지 않는다. 이것은 하나의 상태이다. dp는 같은 문제를 통계하는 데 충분한 해답을 가진 다음에 우리가 원하는 문제를 찾아낸다. 그러면 이 문제는 통계 전의 i숫자와num의 종류수이다. 계산이 끝난 후에 0의 개수만 얻으면 된다.그러면 상태 방정식은 dp[i][j]가 i 위치를 표시하고 j의 하위 문자열 개수를 표시하기 쉽다.
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
typedef long long lld;
const int oo=0x3f3f3f3f;
const lld OO=1LL<<61;
const int MOD=1000000007;
lld dp[1005][20005];
int a[1005];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(dp,0,sizeof dp);
for(int i=0;i<=n;i++)
dp[i][10000]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=20000;j++)
{
if(j+a[i]<=20000)
dp[i][j+a[i]]=(dp[i][j+a[i]]+dp[i-1][j]+MOD)%MOD;
if(j-a[i]>=0)
dp[i][j-a[i]]=(dp[i][j-a[i]]+dp[i-1][j]+MOD)%MOD;
}
}
lld ans=0;
for(int i=1;i<=n;i++)
ans=(ans+dp[i][10000]-1+MOD)%MOD;
cout<<ans<<endl;
}
return 0;
}
/**
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
