diff options
| author | Richard Qin <richard.qin.001@gmail.com> | 2026-09-15 08:16:43 +0800 |
|---|---|---|
| committer | Richard Qin <richard.qin.001@gmail.com> | 2026-09-15 08:16:43 +0800 |
| commit | 4022e5c95210631e4aceb08eaf9d9071aa5aefc4 (patch) | |
| tree | a5922559836e45fb3459a3d070367912e1035b1a /tests/sysy_lvX/test3_2.sy | |
| download | rcc-4022e5c95210631e4aceb08eaf9d9071aa5aefc4.tar.gz rcc-4022e5c95210631e4aceb08eaf9d9071aa5aefc4.tar.xz | |
Diffstat (limited to 'tests/sysy_lvX/test3_2.sy')
| -rw-r--r-- | tests/sysy_lvX/test3_2.sy | 64 |
1 files changed, 64 insertions, 0 deletions
diff --git a/tests/sysy_lvX/test3_2.sy b/tests/sysy_lvX/test3_2.sy new file mode 100644 index 0000000..9b11a59 --- /dev/null +++ b/tests/sysy_lvX/test3_2.sy @@ -0,0 +1,64 @@ +int a[35];
+int n;
+int dp[35][35];
+int root[35][35];
+
+void output(int left, int right) {
+ int r;
+
+ if (left>right) {
+ return;
+ }
+ r = root[left][right];
+ putint(r);
+ putch(32);
+ output(left, r-1); //递归左子树
+ output(r+1, right); //递归右子树
+}
+
+int main() {
+ int i;
+ int j;
+ int k;
+ int len;
+
+ n = getint();
+
+ i=1;
+ while (i<=n) {
+ a[i] = getint();
+ dp[i][i] = a[i]; //分数
+ root[i][i] = i; //根节点
+ i=i+1;
+ }
+
+ len=2;
+ while (len<=n) { //遍历区间长度
+ i=1;
+ while (i+len-1<=n) { //遍历起点
+ j = i+len-1; //终点
+ if (dp[i+1][j] + dp[i][i] > dp[i][j]) {
+ dp[i][j] = dp[i+1][j] + dp[i][i];
+ root[i][j] = i;
+ }
+ if (dp[i][j-1] + dp[j][j] > dp[i][j]) {
+ dp[i][j] = dp[i][j-1] + dp[j][j];
+ root[i][j] = j;
+ }
+ k=i+1;
+ while (k<j) {
+ if ((dp[i][k-1] * dp[k+1][j] + dp[k][k]) > dp[i][j]) {
+ dp[i][j] = dp[i][k-1] * dp[k+1][j] + dp[k][k];
+ root[i][j] = k; //记录根
+ }
+ k=k+1;
+ }
+ i=i+1;
+ }
+ len=len+1;
+ }
+ putint(dp[1][n]);
+ putch(10);
+ output(1,n); //输出前序遍历
+ return 0;
+}
\ No newline at end of file |