結果

問題 No.1867 Partitions and Inversions
ユーザー gew1fw
提出日時 2025-06-12 19:47:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,598 bytes
コンパイル時間 368 ms
コンパイル使用メモリ 81,884 KB
実行使用メモリ 154,644 KB
最終ジャッジ日時 2025-06-12 19:47:20
合計ジャッジ時間 6,916 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    P = list(map(int, sys.stdin.readline().split()))
    
    # 计算整个数组的原始逆序对数目
    def count_inversion(arr):
        n = len(arr)
        res = 0
        for i in range(n):
            for j in range(i+1, n):
                if arr[i] > arr[j]:
                    res +=1
        return res
    
    # 计算区间 [l, r] 中的逆序对数目，其中 l 和 r 是1-based的
    def get_cnt(l, r):
        if l > r:
            return 0
        sub = P[l-1:r]
        return count_inversion(sub)
    
    T = get_cnt(1, N)
    
    # 预处理每个区间[l, r]的逆序对数目
    max_n = N
    cnt = [[0]*(max_n+2) for _ in range(max_n+2)]
    for l in range(1, N+1):
        for r in range(l, N+1):
            cnt[l][r] = get_cnt(l, r)
    
    # 动态规划
    dp = [[-1]*(N+2) for _ in range(N+2)]
    dp[0][0] = 0
    
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(0, i):
                if dp[k-1][j] == -1:
                    continue
                current = dp[k-1][j] + cnt[j+1][i]
                if dp[k][i] < current:
                    dp[k][i] = current
    
    # 计算每个k的结果
    result = []
    for k in range(1, N+1):
        max_sum = 0
        for i in range(1, N+1):
            if dp[k][i] > max_sum:
                max_sum = dp[k][i]
        res = T - max_sum
        result.append(res)
    
    # 输出结果
    for res in result:
        print(res)

if __name__ == "__main__":
    main()
0