동적 계획 - CodeForces - 812B
9671 단어 ACM_동적 기획
The building consists of n floors with stairs at the left and the right sides. Each floor has m rooms on the same line with a corridor that connects the left and right stairs passing by all the rooms. In other words, the building can be represented as a rectangle with n rows and m + 2 columns, where the first and the last columns represent the stairs, and the m columns in the middle represent rooms.
Sagheer is standing at the ground floor at the left stairs. He wants to turn all the lights off in such a way that he will not Go upstairs until all lights in the floor he is standing at are off. Of course, Sagheer must visit a room to turn the light there off. It takes one minute for Sagheer to go to the next floor using stairs or to move from the current room/stairs to a neighboring room/stairs on the same floor. It takes no time for him to switch the light off in the room he is currently standing in. Help Sagheer find the minimum total time to turn off all the lights.
Note that Sagheer does not have to go back to his starting position, and he does not have to visit rooms where the light is already switched off.
Input The first line contains two integers n and m (1 ≤ n ≤ 15 and 1 ≤ m ≤ 100) — the number of floors and the number of rooms in each floor, respectively.
The next n lines contains the building description. Each line contains a binary string of length m + 2 representing a floor (the left stairs, then m rooms, then the right stairs) where 0 indicates that the light is off and 1 indicates that the light is on. The floors are listed from top to bottom, so that the last line represents the ground floor.
The first and last characters of each string represent the left and the right stairs, respectively, so they are always 0.
Output Print a single integer — the minimum total time needed to turn off all the lights.
Example Input 2 2 0010 0100 Output 5 Input 3 4 001000 000010 000010 Output 12 Input 4 3 01110 01110 01110 01110 Output 18 Note In the first example, Sagheer will go to room 1 in the ground floor, then he will go to room 2 in the second floor using the left or right stairs.
In the second example, he will go to the fourth room in the ground floor, use right stairs, go to the fourth room in the second floor, use right stairs again, then go to the second room in the last floor.
In the third example, he will walk through the whole corridor alternating between the left and right stairs at each floor.
,dp[ ][ ], 。 ~
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int INF_INT = 0x3f3f3f3f;
const ll INF_LL = 1e18;
const int MAXN =1e5+5;
const int MAXM = 1015;
int n,m;
int l[20];
int r[20];
int mm[20][105];
int dp[20][2];
string s;
int main()
{
// ios_base::sync_with_stdio(false);
// freopen("data.txt","r",stdin);
memset(dp,0,sizeof(dp));
cin >> n>>m;
m+=2;
for(int i=0;icin >>s;
for(int j=0;jif(s[j]=='0')
{
mm[n-1-i][j]=0;
}
else
{
mm[n-1-i][j]=1;
}
}
}
for(int i=0;iint j;
for(j=0;j1;j++)
{
if(mm[i][j])
{
l[i] = j;
break;
}
}
if(j==m-1)
l[i]=m-1;
l[i] = m-1-l[i];
// cout<
}
for(int i=0;iint j;
for(j=m-1;j>0;j--)
{
if(mm[i][j])
{
r[i] = j;
break;
}
}
if(j==0)
r[i] = 0;
// cout<
}
int tmp_n=n-1;
while(r[tmp_n]==0)
{
tmp_n--;
if(tmp_n<0)
{
cout<<0<return 0;
}
}
dp[0][0] = (r[0]);
if(l[0]==0)
{
dp[0][1] = m-1;
}
else
{
dp[0][1] = (r[0]+l[0]-(m-1-r[0]));
}
for(int i=1;i<=tmp_n;i++)
{
dp[i][0] = min(dp[i-1][0]+1+r[i-1],dp[i-1][1]+1+m-1-l[i-1])+r[i];
dp[i][1] = min(dp[i-1][0]+1+m-1-r[i-1],dp[i-1][1]+1+l[i-1])+l[i];
}
// for(int i=0;i<=tmp_n;i++)
// {
// cout<
// }
cout<0 ],dp[tmp_n][1])<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA 1025_A Spy in the Metro[제의] (소자서) 한 사람이 플랫폼 1에서 출발하면 차를 타려면 시간 T에 플랫폼 n에 도착해야 한다. 플랫폼에서 차를 기다리는 시간이 가장 짧기 때문에 그녀는 두 방향의 열차를 타고 버스가 정차할 때 갈아타야 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.