낙곡2511 [HAOI2008] 막대기 분할
사고방식: 우선 2분의 1로 가장 큰 길이를 매거한다.
pp[i][j]는 앞의 나무 막대기를 표시하고 j칼이 조건에 부합되는 방안의 수를 잘랐다.
dp[i][j]+=dp[k][j-1] (sum[i]-sum[k]<=ans)
이 이전은 접두사와 유지보수를 사용할 수 있습니다.
총 상태 O(n*m), 이동 O(1)
#include
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=b;i>=a;i--)
using namespace std;
#define ll long long
const int N=3e5+5;
const int mod = 998244353;
int n,k,pre,now;
int dp[1100];
short int sum[50010][1010];
int a[50101],ans,L[50100];
ll rd()
{
ll x=0,f=1;char ch=getchar();
while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool check(int x)
{
int sum=0,cnt=0;
rep(i,1,n)
{
if(a[i]>x) return 0;
sum+=a[i];
if(sum>x)
{
sum=a[i];
cnt++;
}
}
return cnt<=k?1:0;
}
void init()
{
n=rd();k=rd();
rep(i,1,n) a[i]=rd();
int l=0,r=1e9;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d ",ans);
int pre,sum=0;
pre=1;
rep(i,1,n)
{
sum+=a[i];
if(sum>ans)
{
while(sum>ans) sum-=a[pre++];
}
L[i]=pre;
//printf(" %d
",L[i]);
}
}
void work()
{
dp[0]=1;
rep(i,2,n)
{
rep(j,0,k)
{
sum[i-1][j]=(sum[i-2][j]+dp[j])%10007;
}
if(L[i]==1) dp[0]=1;
else dp[0]=0;
rep(j,1,k)
{
if(L[i]-2<0) dp[j]=sum[i-1][j-1];
else dp[j]=(sum[i-1][j-1]-sum[L[i]-2][j-1]+10007)%10007;
//printf("%d ",dp[j]);
}
//printf("
");
}
int sum=0;
rep(i,0,k) sum=(sum+dp[i])%10007;
printf("%d
",sum);
}
int main()
{
init();
work();
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
낙곡-훈련장-초보촌-과정함수와 귀속-P1036선수설명: n에서 k개의 수를 구하는 것에 관하여 C(n,k)의 구체적인 추출법은 귀속으로 실현할 수 있다. 소수에 대한 판단:...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.