URAL 1900 Brainwashing Device(dp, 레벨 4)
Crawling in process...
Crawling failed
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit
Status
Practice
URAL 1900
Description
While some people travel in space from planet to planet and discover new worlds, the others who live on Earth still have to get up in the morning, go to work, return back home and try to have a rest. They don't like this situation anymore and envy people who can afford space travel.
That doesn't suit the government of the Earth. Their goal is to make everyone happy, but that is difficult. That is why the government decided to do some tests in the small town of Lux, and then, if everything goes well, to apply the experience to other cities.
Lux's distinctive feature is that it is situated in a long underground tunnel and there is only one train inside it. Almost everyone in the town uses the train. The government has bought a brainwashing device and installed it in the train. The device is new and its effects aren't well understood yet, so the government decided to limit the number of the spans where the device would be turned on. Statistics on number of passengers travelling between each pair of stations every morning have already been collected. Now the government should pick the spans where the device could be used to make most of the people happy.
Input
The first line contains integers
n and
k that are the total number of the stations and the number of spans between adjacent stations where the device could be turned on (2 ≤
n ≤ 500; 1 ≤
k ≤
n − 1). The
i'th of the next
n − 1 lines contains
n −
i integers. The
j'th integer is the number of passengers traveling from
i'th to (
i +
j)'th station. These numbers are non-negative and don't exceed 100. You can assume that every passenger uses the train only once a day.
Output
In the first line output the total number of people who will become happy because of the device. In the second line output
k integers in the ascending order that are the indexes of the spans where the device should be turned on. The span between the station
i and
i + 1 has the index
i. If the problem has multiple solutions you can output any of them.
Sample Input
input
output
4 1
5 0 6
5 3
5
14
3
사고방식: dp[i][K] 앞의 i개는 K개의 최우수치를 선택했고 i는 반드시 선택했다. 어려운 문제가 아니라 dis[i][j]가 얻은 값을 미리 처리하고 j가 중복한 값을 넣었다.
갱: 모두 올려야 하고 순서를 올려야 한다
#include<iostream>
#include<cstring>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define clr(f,z) memset(f,z,sizeof(f))
using namespace std;
const int oo=0x3f3f3f3f;
const int mm=550;
int g[mm][mm],dis[mm][mm],c[mm][mm];
int f[mm],dp[mm][mm],pre[mm][mm],res[mm];
bool vis[mm];
int n,K;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y,int z)
{
for(int i=x;i<mm;i+=lowbit(i))
for(int j=y;j<mm;j+=lowbit(j))
c[i][j]+=z;
}
int query(int x,int y)
{ int ret=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
ret+=c[i][j];
return ret;
}
void print(int x,int k)
{ vis[x]=1;
if(pre[x][k]!=-1)
{print(pre[x][k],k-1);
//printf(" %d",x);
}
else //printf("%d",x);
{ --k;
FOR(i,1,n)
if(vis[i])
printf("%d ",i);
else if(k)
printf("%d ",i),k--;
}
}
int main()
{ int x;
while(~scanf("%d%d",&n,&K))
{ clr(c,0);
FOR(i,1,n-1)
FOR(j,i,n-1)
{scanf("%d",&x);
add(i,j,x);
}
--n;
FOR(i,1,n)
FOR(j,i,n)
dis[i][j]=query(i,n)-query(i,j-1);
clr(dp,0);
clr(pre,-1);
FOR(i,1,n)dp[i][1]=dis[i][i];/// i
FOR(i,2,K)
FOR(j,i,n)//j i
{ dp[j][i]=dp[j][i-1];
FOR(k,1,j-1)
if(dp[j][i]<dp[k][i-1]+dis[j][j]-dis[k][j])
dp[j][i]=dp[k][i-1]+dis[j][j]-dis[k][j],pre[j][i]=k;
// printf("zd=%d %d %d
",j,i,dp[j][i]);
}
clr(vis,0);
int ans=-1,id;
FOR(i,1,n)
if(dp[i][K]>ans)
ans=dp[i][K],id=i;
printf("%d
",ans);
print(id,K);
printf("
");
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.