hdu 1422 월드컵 리바이벌 (최대 연속 서브섹션 및 변형)
1928 단어 System
동적 전환 방정식:
만약 dp[i-1].v>=0 && dp[i-1].v+arr[i]>=0
dp[i].v=dp[i-1].v+arr[i], dp[i].sum=dp[i-1].sum+1;
그렇지 않은 경우: dp[i].v=arr[i],
어떻게 중복을 방지합니까?
1. 만약에 i>n&dp[i].v<0, 끝낼 수 있음;
2.dp[i].sum>=n도 순환을 종료합니다. n 개 이상이어야 하기 때문입니다
3. 1, 2, 1 이 데이터를 주의하기 때문에 n==1은 직접 판단하고 n>=2는 순환하기 시작한다
4. 주의, dp[i-1].v<0시,if(arr[i]>=0)dp[i].sum=1;
#include<iostream>#include<cstdio>
using namespace std;
struct node
{
int v,num;
}dp[210000];
int arr[210000];
int main()
{
int n,w,l;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%d %d",&w,&l);
arr[i]=w-l;
arr[i+n]=w-l;// arr
}
/*for(int i=1;i<=2*n;i++)
printf("%d ",arr[i]);
printf("
");*/
memset(dp,0,sizeof(dp));
dp[1].v=arr[1];
if(dp[1].v>=0)
dp[1].num=1;
else
dp[1].num=0;
if(n>=2)
{
for(int i=2;i<=2*n;i++)
{
if(i>n && dp[i].v<0)
break;
if(dp[i-1].v>=0)
{
if((dp[i-1].v+arr[i])>=0)
{
dp[i].v=dp[i-1].v+arr[i];
dp[i].num=dp[i-1].num+1;
if(dp[i].num>=n)
break;
}
else
{
dp[i].v=arr[i];
if(arr[i]>=0)
dp[i].num=1;
else
dp[i].num=0;
}
}
else
{
dp[i].v=arr[i];
if(arr[i]>=0)
dp[i].num=1;
else
dp[i].num=0;
}
}
}
int ans=0;
for(int i=1;i<=2*n;i++)
if(dp[i].num>ans)
ans=dp[i].num;
printf("%d
",ans);
}
system("pasue");
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Bring application to foreground with a keypressFrom Forum Nokia Wiki Inorder to capture the keys while you application under background you've to override CCoeAppUi::H...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
