CF-div2-637-D. Nastya and Scoreboard | dp 욕심 기억화 검색
아이디어 1
ffs 메모리 검색
생각 2
욕심
뒤에서 앞으로 i개까지 총 얼마를 썼는지 열거하면 dp[i][i개까지 총 비용] |= dp[i+1][i개까지 총 비용 - i개의cost 비용]
dp 코드
#include
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 2e3+100;
const string str[] = {"1110111","0010010","1011101","1011011","0111010","1101011","1101111","1010010","1111111","1111011"};
string s;
int val[maxn][10];
int dp[maxn][maxn];
void init(int pos){
for(int i=0;i<=9;i++){
bool flag=false;
int cnt=0;
for(int j=0;j<7;j++){
if(str[i][j]!=s[j]){
if(s[j]=='1'){
flag=true;
break;
}
cnt++;
}
}
if(flag) val[pos][i] = -1;
else val[pos][i] = cnt;
}
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
cin>>s;
init(i);
}
dp[n+1][0]=true; // : n+1 0
for(int i=n;i>=1;i--){
for(int j=0;j<=9;j++){ // i j
int cost = val[i][j]; // i cost j
if(cost == -1) {
dp[i][cost] = 0;
continue;
}
for(int t = cost;t<=k;t++){
dp[i][t] |= dp[i+1][t-cost];
}
}
}
if(!dp[1][k]) return 0*puts("-1");
//
string ans;
for(int i=1;i<=n;i++){
for(int j=9;j>=0;j--){
if(val[i][j]!=-1 && dp[i+1][k-val[i][j]] == 1){
k -= val[i][j];
ans += to_string(j);
break;
}
}
}
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
