1274
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> using namespace std; const int inf = 10000000; int f[110][110],tot[110],a[110],n; int dfs(int l,int r) { if (f[l][r] != -1) return f[l][r]; int minn = inf; for (int k = l;k <= r - 1;k++) minn = min(minn,dfs(l,k) + dfs(k + 1,r) + tot[r] - tot[l - 1]); return f[l][r] = minn; } int main() { memset(f,-1,sizeof(f));//memset 只有-1和0可以用，值是精准的。 scanf("%d",&n); for (int i = 1;i <= n;i++) { scanf("%d",&a[i]); tot[i] = tot[i - 1] + a[i]; f[i][i] = 0; } printf("%d ",dfs(1,n)); return 0; }
1275
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> using namespace std; int n,k,f[20][20],num[20]; char s[20]; int get_num(int x,int y) { int res = 0; for (int i = x;i <= y;i++) { res *= 10; res += num[i]; } return res; } int main() { scanf("%d%d%s",&n,&k,s + 1); for (int i = 1;i <= n;i++) { num[i] = s[i] - '0'; } for (int i = 1;i <= n;i++) { f[i][0] = get_num(1,i); // printf("f[%d][0] = %d ",i,f[i][0]); } for (int l = 1;l <= k;l++) for (int i = l + 1;i <= n;i++) for (int j = l;j <= i - 1;j++) f[i][l] = max(f[i][l],f[j][l-1] * get_num(j + 1,i)); printf("%d ",f[n][k]); return 0; }
1276
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 9 int f[2100][2100],len1,len2; 10 char str1[2100],str2[2100]; 11 int main() 12 { 13 scanf("%s%s",str1 + 1,str2 + 1); 14 len1 = strlen(str1 + 1); 15 len2 = strlen(str2 + 1); 16 memset(f,0x1f,sizeof(f)); 17 f[0][0] = 0; 18 for (int i = 1;i <= len1;i++) 19 f[i][0] = i; 20 for (int i = 1;i <= len2;i++) 21 f[0][i] = i; 22 for (int i = 1;i <= len1;i++) 23 for (int j = 1;j <= len2;j++) 24 { 25 if (str1[i] == str2[j]) 26 { 27 f[i][j] = f[i - 1][j - 1]; 28 }else 29 { 30 f[i][j] = min(f[i][j],f[i - 1][j - 1] + 1); 31 f[i][j] = min(f[i][j],f[i][j - 1] + 1); 32 f[i][j] = min(f[i][j],f[i - 1][j] + 1); 33 } 34 } 35 printf("%d ",f[len1][len2]); 36 } 37 /*#include <cstdio> 38 #include <cstring> 39 #include <cmath> 40 #include <algorithm> 41 #include <vector> 42 #include <queue> 43 using namespace std; 44 int n,k,f[20][20],num[20]; 45 char s[20]; 46 int get_num(int x,int y) 47 { 48 int res = 0; 49 for (int i = x;i <= y;i++) 50 { 51 res *= 10; 52 res += num[i]; 53 } 54 return res; 55 } 56 int main() 57 { 58 scanf("%d%d%s",&n,&k,s + 1); 59 for (int i = 1;i <= n;i++) 60 { 61 num[i] = s[i] - '0'; 62 } 63 for (int i = 1;i <= n;i++) 64 { 65 f[i][0] = get_num(1,i); 66 } 67 for (int l = 1;l <= k;l++) 68 for (int i = l + 1;i <= n;i++) 69 for (int j = l;j <= i - 1;j++) 70 f[i][l] = max(f[i][l],f[j][l-1] * get_num(j + 1,i)); 71 printf("%d ",f[n][k]); 72 return 0; 73 } 74 */ 75 /* 76 1 77 #include <cstdio> 78 #include <cstring> 79 #include <cmath> 80 #include <algorithm> 81 #include <vector> 82 #include <queue> 83 using namespace std; 84 const int inf = 10000000; 85 int f[110][110],tot[110],a[110],n; 86 int dfs(int l,int r) 87 { 88 if (f[l][r] != -1) 89 return f[l][r]; 90 int minn = inf; 91 for (int k = l;k <= r - 1;k++) 92 minn = min(minn,dfs(l,k) + dfs(k + 1,r) + tot[r] - tot[l - 1]); 93 return f[l][r] = minn; 94 } 95 int main() 96 { 97 memset(f,-1,sizeof(f));//memset 只有-1和0可以用，值是精准的。 98 scanf("%d",&n); 99 for (int i = 1;i <= n;i++) 100 { 101 scanf("%d",&a[i]); 102 tot[i] = tot[i - 1] + a[i]; 103 f[i][i] = 0; 104 } 105 printf("%d ",dfs(1,n)); 106 return 0; 107 } 108 */
1277
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> using namespace std; int n,vec[110][110],mp[110][110],dp[110][110][110],sum[110]; int main() { scanf("%d",&n); int tx,ty,tv; while (scanf("%d%d%d",&tx,&ty,&tv) > 0 && (tx + ty + tv)) mp[tx][ty] = tv; for (int i = 1;i <= n;i++) for (int j = 1;j <= n;j++) { int tp = i + j - 1; sum[tp]++; vec[tp][sum[tp]] = mp[i][j]; } dp[1][1][1] = vec[1][1]; for (int mi = 2;mi <= n;mi++) for (int j = 1;j <= sum[mi];j++) for (int o = 1;o <= sum[mi];o++) { int maxn = 0; maxn = max(dp[mi - 1][j][o - 1],max(dp[mi - 1][j - 1][o],max(dp[mi - 1][j][o],dp[mi - 1][j - 1][o - 1]))); if (j != o) dp[mi][j][o] = maxn + vec[mi][j] + vec[mi][o]; else dp[mi][j][o] = maxn + vec[mi][j]; } for (int mi = n + 1;mi <= 2 * n - 1;mi++) for (int j = 1;j <= sum[mi];j++) for (int o = 1;o <= sum[mi];o++) { int maxn = 0; maxn = max(dp[mi - 1][j][o + 1],max(dp[mi - 1][j + 1][o],max(dp[mi - 1][j][o],dp[mi - 1][j + 1][o + 1]))); if (j != o) dp[mi][j][o] = maxn + vec[mi][j] + vec[mi][o]; else dp[mi][j][o] = maxn + vec[mi][j]; } printf("%d ",dp[2 * n - 1][1][1]); return 0; }
1278
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int MAXN = 510; 6 int a[MAXN],b[MAXN],c[MAXN][MAXN],sum[MAXN],f[MAXN][MAXN],m,n; 7 int main() 8 { 9 scanf("%d%d",&m,&n); 10 for (int i = 1;i <= m;i++) 11 { 12 scanf("%d",&a[i]); 13 sum[i] = sum[i - 1] + a[i]; 14 } 15 sum[0] = 0; 16 memset(f,0x1f,sizeof(f)); 17 for (int i = 1;i <= m;i++) 18 f[1][i] = sum[i]; 19 for (int i = 2;i <= n;i++) 20 for (int j = 1;j <= m;j++) 21 for (int k = i - 1;k < j;k++) 22 f[i][j] = min(f[i][j],max(f[i - 1][k],sum[j] - sum[k])); 23 int maxn = f[n][m]; 24 int tmp = n;//当前把第i本 分给谁 25 for (int i = m;i >= 1;i--) 26 { 27 if (a[i] + b[tmp] > maxn) 28 tmp = tmp - 1; 29 b[tmp] += a[i]; 30 c[tmp][++c[tmp][0]] = i;//第tmp个人，抄的c[tmp][0]本书 31 } 32 for (int i = 1;i <= n;i++) 33 { 34 printf("%d %d ",c[i][c[i][0]],c[i][1]); 35 } 36 return 0; 37 }
1279
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 int n,m,dp[110][110],a[110][100],ans[110]; 9 int main() 10 { 11 scanf("%d%d",&m,&n); 12 for (int i = 1;i <= m;i++) 13 for (int j = 1;j <= n;j++) 14 scanf("%d",&a[i][j]); 15 for (int i = 0;i <= m;i++) 16 for (int j = 0;j <= n;j++) 17 dp[i][j] = -1000000000; 18 for (int i = 0;i <= n;i++) 19 dp[0][i] = 0; 20 for (int i = 1;i <= m;i++) 21 for (int j = i;j <= n;j++) 22 { 23 if (dp[i][j] < dp[i - 1][j - 1] + a[i][j]) 24 { 25 dp[i][j] = dp[i - 1][j - 1] + a[i][j]; 26 // frm[i][j] = dat(i-1,j-1) 27 } 28 if (dp[i][j] < dp[i][j - 1]) 29 { 30 dp[i][j] = dp[i][j - 1]; 31 // frm[i][j] = dat(i,j-1) 32 } 33 } 34 printf("%d ",dp[m][n]); 35 int val = dp[m][n]; 36 for (int i = m;i >= 1;i--) 37 for (int j = i;j <= n;j++) 38 if (dp[i][j] == val) 39 { 40 ans[i] = j; 41 val -= a[i][j]; 42 break; 43 } 44 for (int i = 1;i <= m;i++) 45 printf("%d ",ans[i]); 46 return 0; 47 }
1280
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 const int MAXN = 510; 9 int mx[] = {-1,1,0,0},my[] = {0,0,-1,1},r,c,mp[MAXN][MAXN],dp[MAXN][MAXN],ans; 10 int dfs(int x,int y) 11 { 12 if (dp[x][y] != 0) 13 return dp[x][y]; 14 int maxn = 1; 15 for (int i = 0;i <= 3;i++) 16 { 17 int xx = x + mx[i]; 18 int yy = y + my[i]; 19 if (xx <= 0 || xx >= r + 1 || yy <= 0 || yy >= c + 1) 20 continue; 21 if (mp[xx][yy] < mp[x][y]) 22 maxn = max(dfs(xx,yy) + 1,maxn); 23 } 24 return dp[x][y] = maxn; 25 26 } 27 int main() 28 { 29 scanf("%d%d",&r,&c); 30 for (int i = 1;i <= r;i++) 31 for (int j = 1;j <= c;j++) 32 scanf("%d",&mp[i][j]); 33 for (int i = 1;i <= r;i++) 34 for (int j = 1;j <= c;j++) 35 ans = max(ans,dfs(i,j)); 36 printf("%d ",ans); 37 return 0; 38 }
1285
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 int n,res,a[1100],f[1100]; 9 int main() 10 { 11 scanf("%d",&n); 12 for (int i = 1;i <= n;i++) 13 scanf("%d",&a[i]); 14 f[1] = a[1]; 15 for (int i = 2;i <= n;i++) 16 { 17 f[i] = a[i]; 18 for (int j = 1;j < i;j++) 19 if (a[j] < a[i]) 20 f[i] = max(f[i],f[j] + a[i]); 21 } 22 for (int i = 1;i <= n;i++) 23 res = max(res,f[i]); 24 printf("%d ",res); 25 return 0; 26 }
1299
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 int n,k; 9 int a[110],f[110][110]; 10 int main() 11 { 12 scanf("%d%d",&n,&k); 13 for (int i = 1;i <= n;i++) 14 scanf("%d",&a[i]); 15 memset(f,-1,sizeof(f)); 16 f[0][0] = 0; 17 for (int i = 1;i <= n;i++) 18 for (int j = 0;j < k;j++) 19 { 20 //f[i][j] = max(f[i - 1][j],f[i - 1][(j - a[i] % k + k) %k] + a[i]); 21 if (f[i - 1][j] != -1) 22 f[i][j] = max(f[i][j],f[i - 1][j]); 23 if (f[i - 1][(j - a[i] % k + k) %k] != -1) 24 f[i][j] = max(f[i][j],f[i - 1][(j - a[i] % k + k) %k] + a[i]); 25 } 26 printf("%d ",f[n][0]); 27 return 0; 28 }
1300
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 int n,m,f[110][20]; 9 int main() 10 { 11 while (scanf("%d%d",&n,&m) > 0) 12 { 13 for (int i = 1;i <= n;i++) 14 for (int j = 1;j <= m;j++) 15 f[i][j] = i; 16 17 for (int j = 1;j <= n;j++) 18 for (int i = 2;i <= m;i++) 19 for (int k = 1;k <= j;k++) 20 f[j][i] = min(f[j][i],max(f[k - 1][i - 1],f[j - k][i]) + 1); 21 printf("%d ",f[n][m]); 22 } 23 return 0; 24 }
1301
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 int T,n; 5 int f[110000][2],a[110000]; 6 int main() 7 { 8 for (scanf("%d",&T);T;T--) 9 {//多组数据一定考虑初始化 10 scanf("%d",&n); 11 for (int i = 1;i <= n;i++) 12 scanf("%d",&a[i]); 13 for (int i = 1;i <= n;i++) 14 { 15 f[i][0] = max(f[i - 1][1],f[i - 1][0]); 16 f[i][1] = f[i - 1][0] + a[i]; 17 } 18 printf("%d ",max(f[n][0],f[n][1])); 19 } 20 return 0; 21 }
1302
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 const int inf = 10000000; 5 int T,n,minn,maxn,res,a[110000],f[110000],g[110000]; 6 int main() 7 { 8 scanf("%d",&T); 9 while (T--) 10 { 11 //初始化的问题 12 res = 0; 13 minn = inf; 14 maxn = -inf; 15 scanf("%d",&n); 16 for (int i = 1;i <= n;i++) 17 scanf("%d",&a[i]); 18 f[0] = g[n + 1] = 0;//可有可无 19 //f 20 for (int i = 1;i <= n;i++) 21 { 22 minn = min(minn,a[i]); 23 f[i] = max(f[i - 1],a[i] - minn); 24 } 25 //g 边界其实是n+1 26 for (int i = n;i >= 1;i--) 27 { 28 maxn = max(maxn,a[i]); 29 g[i] = max(g[i + 1],maxn - a[i]); 30 } 31 //ans 32 for (int i = 1;i <= n;i++) 33 res = max(res,f[i] + g[i]); 34 printf("%d ",res); 35 } 36 }
1303
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 int T,m,n; 9 int f(int m,int n) 10 { 11 if (m == 0 || n == 1) 12 return 1; 13 if (m < n) 14 return f(m,m); 15 return f(m,n - 1) + f(m - n,n); 16 } 17 int main() 18 { 19 20 scanf("%d",&T); 21 for (int i = 1;i <= T;i++) 22 { 23 scanf("%d%d",&m,&n); 24 printf("%d ",f(m,n)); 25 } 26 return 0; 27 }
1305
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 int ldp[51000],rdp[51000],lsum[51000],rsum[51000],a[51000],T,n,res; 9 int main() 10 { 11 scanf("%d",&T); 12 while (T--) 13 { 14 memset(lsum,0,sizeof(lsum)); 15 memset(rsum,0,sizeof(rsum)); 16 res = 0; 17 scanf("%d",&n); 18 for (int i = 1;i <= n;i++) 19 scanf("%d",&a[i]); 20 lsum[1] = a[1]; 21 for (int i = 2;i <= n;i++) 22 if (lsum[i - 1] > 0) 23 lsum[i] = lsum[i - 1] + a[i]; 24 else 25 lsum[i] = a[i]; 26 rsum[n] = a[n]; 27 for (int i = n - 1;i >= 1;i--) 28 if (rsum[i + 1] > 0) 29 rsum[i] = rsum[i + 1] + a[i]; 30 else 31 rsum[i] = a[i]; 32 // lsum[i] 以a[i]结尾的最大子段和 33 // rsum[i] 以a[i]开头的最大字段和。 34 35 ldp[1] = lsum[1]; 36 for (int i = 2;i <= n;i++) 37 ldp[i] = max(ldp[i - 1],lsum[i]); 38 rdp[n] = rsum[n]; 39 for (int i = n - 1;i >= 1;i--) 40 rdp[i] = max(rdp[i + 1],rsum[i]); 41 for (int i = 1;i <= n - 1;i++) 42 res = max(res,ldp[i] + rdp[i + 1]); 43 printf("%d ",res); 44 } 45 return 0; 46 }