头像

东D


访客:307

离线:1天前



东D
2个月前

题目描述

给你一根长度为 n 绳子,请把绳子剪成 m 段(m、n 都是整数,2≤n≤58 并且 m≥2)。

每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少?

例如当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到最大的乘积18。

样例

样例

输入:8

输出:18

在看到这道题时,我的第一反应就是动态规划
因为只有小于length的数剪出的值乘积最大可以推出到length拆开的数都是最大的

例如我们多推几个数
2--------1 1
3--------1 2
4--------1 3 或 2 2
5--------1 4 或 2 3
6--------1 5 或 2 4 或 3 3
7--------1 6 或 2 5 或 3 4
8--------1 7 或 2 6 或 3 5 或 4 4

由于最少都要剪2段,我就都让它由2段表示,而且可以肯定最大值就在这些组合中(因为这些数又可以拆除其他数)

2拆后的最大数为1

3可以拆除1 2
而2我们可以有两种情况

1. 2不动,也就是不拆
2. 2拆除最大,而2我们知道最大是1

这两种情况让我们知道,肯定是直接选2更合适,选择不拆

后面的数也是这样判断
我们判断的规则就是
本身的这个数 和 把这个数拆成最大值 相比较 看谁更大
谁更大我就选谁呗


C++ 代码

int f[60];
class Solution {
public:
    int maxProductAfterCutting(int length) {
        if(length == 2 || length == 3) return length - 1;
        f[1] = 1;
        f[2] = 1;
        f[3] = 2;
        for(int i = 4; i <= length; i++)
        {
            int a, b;
            for(int j = 1; j <= i / 2; j++)
            {
                a = j;
                b = i - j;
                f[i] = max(f[i], a * b);
                f[i] = max(f[i], a * f[b]);
                f[i] = max(f[i], f[a] * b);
                f[i] = max(f[i], f[a] * f[b]);
            }
        }
        return f[length];
    }
};



东D
2个月前

题目描述

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留。

样例1

输入:1->2->3->3->4->4->5

输出:1->2->5

样例2

输入:1->1->1->2->3

输出:2->3


C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;

        map<int, int> m;
        ListNode* p = head;
        //将每个数字出现的次数统计出来
        while(p != NULL)
        {
            m[p->val]++;
            p = p->next;
        }

        //分为前后指针,好进行删除操作
        ListNode* hh = head;
        ListNode* tt = head->next;

        while(tt != NULL)
        {
            //取出结点tt
            if(m[tt->val] > 1) hh->next = tt->next; //当前结点出现多次,将hh结点指针指向tt的下一个结点
            else hh = hh->next; //tt结点只出现一次,hh向后移动

            //tt向后移动
            tt = tt->next;
        }
        //如果剩下的第一个结点也是出现多次的,分只剩下一个和多个的情况
        if(m[head->val] > 1)
        {
            if(head->next == NULL) return NULL; //只剩下一个直接返回
            else head = head->next; //向后挪动一个位置进行返回
        }
        return head;
    }
};



东D
4个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2+5;
int k, n, ax, ay, bx, by;
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
char path[N][N];
bool f, vis[N][N];
bool in(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < n;
}
bool dfs(int x, int y){
    if(x == bx && y == by){
        return true;
    }
    int nx, ny; 
    for(int i = 0; i < 4; i++){
        nx = x + dir[i][0];
        ny = y + dir[i][1];
        if(in(nx, ny) && path[nx][ny] == '.' && !vis[nx][ny]) {
            vis[nx][ny] = true;
            if(dfs(nx, ny)) return true;
            vis[nx][ny] = false;
        }
    }
    return false;
}
int main()
{
    cin >> k;
    while(k--){

        f = false;
        scanf("%d",&n);
        for(int i = 0; i < n; i++) scanf("%s",path[i]);
        scanf("%d%d",&ax, &ay);
        scanf("%d%d",&bx, &by);

        if(ax == bx && ay == by) {
            cout << "YES" << endl;
            continue;
        }
        if(path[ax][ay] == '#' || path[bx][by] == '#') {
            cout << "NO" << endl;
            continue;
        }
            vis[ax][ay] = true;
            if(dfs(ax, ay)) cout << "YES" << endl;
            else cout << "NO" << endl;
        memset(vis, false, sizeof(vis));
    }
    return 0;
} 



东D
4个月前

自底向上考虑可以省去边界问题和判断f[n][1]–f[n][n]的最大值

直接在存数的数组里进行更新就行

#include<iostream>
using namespace std;
int n, a[505][505];
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            scanf("%d",&a[i][j]);
    for(int i = n-1; i >= 1; i--)
        for(int j = 1; j <= i; j++)
            a[i][j] = max(a[i+1][j], a[i+1][j+1]) + a[i][j];
    cout << a[1][1];
    return 0;
}