[JZOJ B 팀] [NOIP 2015 시 뮬 레이 션 10.22] WTF 교환
N 개의 정 수 를 포함 하 는 배열 A 를 가정 하고 N + 1 개의 정 수 를 포함 하 는 배열 ID 와 정수 R 을 제공 합 니 다.그 중에서 ID 배열 의 정 수 는 모두 구간 [1, N - 1] 에 있다.아래 의 알고리즘 으로 A 를 Warshall - Turing - Furier 변환 (WTF):
sum = 0
for i = 1 to N
index = min{ ID[i], ID[i+1] }
sum = sum + A[index]
A R
A
for i = 1 to N
index = max{ ID[i], ID[i+1] }
index = index + 1
sum = sum + A[index]
A R
배열 A 와 정수 R 을 주 었 으 나 배열 ID 는 주지 않 았 다.배열 A 에 대해 WTF 알고리즘 을 실시 한 후에 변수 sum 이 나타 날 수 있 는 최대 치 는 얼마 입 니까?
Input
첫 줄 은 두 개의 정수 N 과 R 을 포함한다.두 번 째 줄 은 N 개의 정 수 를 포함 하고 A [1] 에서 A [N] 의 값 을 대표 합 니 다.
Output
첫 번 째 줄 출력 변수 sum 에 나타 날 수 있 는 최대 값 입 니 다.두 번 째 줄 은 N + 1 개의 정 수 를 포함 하 는 ID 배열 을 출력 합 니 다.ID 배열 의 모든 수 는 구간 [1, N - 1] 에 있어 야 합 니 다.만 족 스 러 운 ID 배열 이 여러 개 있 으 면 임의의 그룹 을 출력 합 니 다.만약 첫 번 째 줄 이 정확 하 다 면 (두 번 째 줄 을 출력 하 든 안 하 든) 이 테스트 포인트 의 50% 점 수 를 얻 을 수 있 습 니 다.
Sample Input
입력 1: 5 3 1 - 1 - 1 1 입력 2: 6 5 5 4 1 3 5
Sample Output
수출 1: 10 1 1 1 2 3 수출 2: 16 3 2 1 1 5 4 1
Data Constraint
20% 의 데이터 에 대해 N < = 7.60% 의 데이터 에 대해 N < = 300.100% 의 데이터 에 대해 2 & lt; = N & gt; = 3000, 1 & gt; = R
사고의 방향
하나의 ID 는 이전 ID 와 만 다음 ID 와 관련 이 있 고 DP 를 고려 한 것 으로 나 타 났 다.
f [i] [j] 를 설정 하면 i 번 째 ID 로 j 의 최대 sum 을 입력 합 니 다.
k > j f [i] [j] = maxf [i − 1] [k] + a [min (j, k)] − a [max (j, k) + 1]
k < = j f [i] [j] = maxf [i - 1] [k] + a [k] - a [j + 1]
a 값 변환 에 주의 하 세 요. 그리고 g [i] [j] 로 앞 구 를 기록 해 야 합 니 다.
코드
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f,maxn=3077;
int n,r,a[maxn],f[maxn][maxn],g[maxn][maxn],ass,t;
void print(int x,int y)
{
if(x!=0) print(x-1,g[x][y]);
printf("%d ",y+1);
}
int main()
{
memset(f,200,sizeof(f));
memset(f[0],0,sizeof(f[0]));
scanf("%d%d",&n,&r);
for(int i=0; i"%d",&a[i]);
for(int i=1; i<=n; i++)
{
ass=-inf;
for(int j=0; j1; j++)
{
if(f[i-1][j]+a[((j-(i-1)*r)%n+n)%n]>ass)
{
ass=f[i-1][j]+a[((j-(i-1)*r)%n+n)%n];
t=j;
}
if(ass-a[((j+1-(i-1)*r)%n+n)%n]>f[i][j])
{
f[i][j]=ass-a[((j+1-(i-1)*r)%n+n)%n];
g[i][j]=t;
}
}
ass=-inf;
for(int j=n-2; j>=0; j--)
{
if(f[i-1][j]-a[((j+1-(i-1)*r)%n+n)%n]>ass)
{
ass=f[i-1][j]-a[((j+1-(i-1)*r)%n+n)%n];
t=j;
}
if(ass+a[((j-(i-1)*r)%n+n)%n]>f[i][j])
{
f[i][j]=ass+a[((j-(i-1)*r)%n+n)%n];
g[i][j]=t;
}
}
}
ass=-inf;
for(int j=0; j1; j++) if(f[n][j]>ass)
{
ass=f[n][j];
t=j;
}
printf("%d
",ass);
print(n,t);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode - 503. 다음 더 큰 요소 II (Next Greater Element II) [중간] - 분석 및 코드 (Java)순환 배열 (마지막 요소 의 다음 요 소 는 배열 의 첫 번 째 요소) 을 지정 하고 모든 요소 의 다음 요 소 를 출력 합 니 다.숫자 x 의 다음 더 큰 요 소 는 배열 에 따라 순 서 를 옮 겨 다 니 는 것 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.