ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 11.09.2019 18:37:35

ამოცანა: სიტყვის შაბლონი

მომხმარებელი: GiorgiNadareishvili

ვერდიქტი: ნაწილობრივი ამოხსნა

შეფასება: 42.9 ქულა







#include <bits/stdc++.h>
using namespace std;

int n, m, A[51], B[51], dp[51][51];
string a, b;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> a >> b;
	n = a.size(), m = b.size();
	a = " " + a, b = " " + b;
	for(int i = 1; i <= n; ++i) {
		A[i] = A[i - 1] + (int)(a[i] != '*');
		dp[i][0] = 1e9;
	}
	for(int i = 1; i <= m; ++i) {
		B[i] = B[i - 1] + (int)(b[i] != '*');
		dp[0][i] = 1e9;
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			dp[i][j] = 1e9;
			if(a[i] == '*') {
				for(int k = 0; k <= j; ++k) {
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + B[j] - B[k]);
				}
			}
			if(b[j] == '*') {
				for(int k = 0; k <= i; ++k) {
					dp[i][j] = min(dp[i][j], dp[k][j - 1] + A[j] - A[k]);
				}
			}
			if(a[i] == '?' || b[j] == '?' || a[i] == b[j]) {
				dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
			}
		}
	}
	cout << dp[n][m] << endl;
    return 0;
}

ტესტები

შემავალი მონაცემები
A*
*B
გამომავალი მონაცემები
2
თქვენი პასუხი
2
ჩეკერის პასუხი
YES
შემავალი მონაცემები
AB?
*BC
გამომავალი მონაცემები
3
თქვენი პასუხი
3
ჩეკერის პასუხი
YES
შემავალი მონაცემები
???
*
გამომავალი მონაცემები
3
თქვენი პასუხი
1
ჩეკერის პასუხი
NO
შემავალი მონაცემები
*AB
CD*
გამომავალი მონაცემები
4
თქვენი პასუხი
4
ჩეკერის პასუხი
YES
შემავალი მონაცემები
AB*CD*EF
A*BC*DE*F
გამომავალი მონაცემები
6
თქვენი პასუხი
8
ჩეკერის პასუხი
NO
შემავალი მონაცემები
*A*A*A*A*A*A*A*A*A*A*A*A*A*A*A*A*A*A*A*A*
*B*B*B*B*B*B*B*B*B*B*B*B*B*B*B*B*B*B*B*B*
გამომავალი მონაცემები
40
თქვენი პასუხი
-70
ჩეკერის პასუხი
NO
შემავალი მონაცემები
A*?*?*?*?*?*?*?*?*?*?B
A?*?*?*?*?*?*?*?*?*?*C
გამომავალი მონაცემები
NO SOLUTION
თქვენი პასუხი
1000000000
ჩეკერის პასუხი
NO