9mean 20200730 solved

9mean · 9mean · commit 6463aa3e8cfa · 2020-07-30T21:58:14.000+09:00
diff --git a/9mean/20200730/11066.txt b/9mean/20200730/11066.txt
@@ -0,0 +1,47 @@
+#include <stdio.h>
+#include <algorithm>
+#include <cstring>
+
+using namespace std;
+
+
+
+int dp[501][501];
+int f[501];
+int sum[501];
+
+int func(int s, int e){
+	if (s >= e) return 0;
+
+	if (dp[s][e] != -1) return dp[s][e];
+	if (e == s + 1) return f[s] + f[e];
+
+	dp[s][e] = 123456789;
+	for (int i = s; i <= e; i++){
+		int tmp = func(s, i) + func(i + 1, e) + sum[e] - sum[s - 1];
+		dp[s][e] = min(dp[s][e], tmp);
+	}
+	return dp[s][e];
+}
+
+int main(){
+
+
+	int t;
+	scanf("%d",&t);	
+	while (t--){
+		int n;
+		scanf("%d",&n);
+		for (int i = 1; i <= n; i++){
+		scanf("%d",&f[i]);
+			sum[i] = sum[i - 1] + f[i];
+		}
+		for (int i = 1; i <= n; i++){
+			for (int j = 1; j <= n; j++){
+				dp[i][j] = -1;
+			}
+		}
+	printf("%d\n",func(1, n) );
+	}
+	return 0;
+}
diff --git a/9mean/20200730/9251.txt b/9mean/20200730/9251.txt
@@ -0,0 +1,31 @@
+#include <stdio.h>
+#include <algorithm>
+#include <cstring>
+#include <stdlib.h>
+using namespace std;
+
+
+int main() {
+	int dp[1001][1001];
+	char a[1001],b[1001];
+	memset(dp,0,sizeof(dp));
+	scanf("%s",&a);
+	getchar();
+	scanf("%s",&b);
+	getchar();
+	int alen=strlen(a);
+	int blen=strlen(b);
+
+	for(int i=1;i<=alen;i++){
+		for(int j=1;j<=blen;j++){
+			if(a[i-1]==b[j-1]){
+				dp[i][j]+=dp[i-1][j-1]+1;
+			}
+			else{
+				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
+			}
+		}
+	}
+	printf("%d",dp[alen][blen]);
+	return 0;
+}
