首頁 北冥有鱼

# 充实的寒假生活 (GREEDY/DP)

描述

寒假马上就要到了，龙傲天同学获得了从第 0 天开始到第 60 天结束为期 61 天超长寒假，他想要尽可能丰富自己的寒假生活。
现提供若干个活动的起止时间，请计算龙同学这个寒假至多可以参加多少个活动？注意所参加的活动不能有任何时间上的重叠，在第 x 天结束的活动和在第 x 天开始的活动不可同时选择。

输入

第一行为整数 n，代表接下来输入的活动个数 (n < 10000)
紧接着的 n 行，每一行都有两个整数，第一个整数代表活动的开始时间，第二个整数代表全结束时间

输出

输出至多参加的活动个数

样例输入

5
0 0
1 1
2 2
3 3
4 4

样例输出

5

解决

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        if not intervals or len(intervals) == 0:
            return 0
        intervals.sort(key = lambda x: x[0])  # 按左端点从小到大排序
        temp_pos = 0
        cnt = 0
        for i in range(1, len(intervals)):
            if intervals[temp_pos][1] >= intervals[i][0]:  # 当当前区间右端点 > i 区间左端点
                if intervals[i][1] < intervals[temp_pos][1]:  # 当 i 区间右端点 & lt; 当前区间右端点，表示 i 区间被覆盖在当前区间中
                    temp_pos = i  # 更新 temp_pos，选择覆盖范围小的 i 区间
                cnt += 1  # 当前区间右端点 > i 区间左端点都要计数 + 1
            else:
                temp_pos = i  # 当当前区间右端点 & lt;=i 区间左端点，表示不重叠，要更新 temp_pos
        return len(intervals)-cnt
if __name__ == "__main__":
    n=int(input())
    intervals=[]
    for i in range(n):
        intervals.append(list(map(int, input().split())))
    print(Solution().eraseOverlapIntervals(intervals))
# 和为给定数
描述
给出若干个整数，询问其中是否有一对数的和等于给定的数。
输入
共三行：
第一行是整数 n (0 < n <= 100,000)，表示有 n 个整数。
第二行是 n 个整数。整数的范围是在 0 到 108 之间。
第三行是一个整数 m（0 <= m <= 230)，表示需要得到的和。
输出
若存在和为 m 的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行 No。
样例输入
4
2 5 1 4
6
样例输出
1 5
解决
def find(key,base,top): #二分查找
    while base<=top:
        mid = (base+top)//2
        if a[mid]==key:
            return True
        elif a[mid]<key: 
            base=mid+1
        else: 
            top=mid-1
    return False 
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
flag=0
# print(a)
m=int(input())
for i in range(n):
    key=m-a[i]
    base=i+1
    top=n-1
    if find(key,base,top):
        print(a[i],key)
        flag=1
        break
if flag==0:
    print("No")
# 求逆序对数
描述
对于一个长度为 N 的整数序列 A ，满足 i < j 且  Ai > Aj . 的数对 (i,j) 称为整数序列 A 的一个逆序
请求出整数序列 A 的所有逆序对个数
输入
输入包含多组测试数据，每组测试数据有两行
第一行为整数 N(1 <= N <= 20000) ，当输入 0 时结束
第二行为 N 个整数，表示长为 N 的整数序列
输出
每组数据对应一行，输出逆序对的个数
样例输入
5
1 2 3 4 5
5
5 4 3 2 1
1
1
0
样例输出
0
10
0
解决 1
冒泡，可能会超时
def main():
    while True:
        n = int(input())
        if n==0:
            return
        ll = list(map(int, input().split()))
        # print(ll)
        c=[0 for i in range(101)]
        group=0
        for i in range(n-1):
            for j in range(i,n-1):
                if ll[j]>ll[j+1]:
                    group+=1
        print(group)
if __name__ == '__main__':
    main()
解决 2
归并
def merge_sort(a):
    s = 0
    if len(a) <= 1: return 0
    mid = len(a) // 2
    l = a[:mid]
    r = a[mid:]
    s += merge_sort(l) + merge_sort(r)
    i = j = k = 0
    while (i < len(l) and j < len(r)):
        if (l[i] <= r[j]):
            a[k] = l[i]
            i += 1
            k += 1
        else:
            a[k] = r[j]
            j += 1
            k += 1
            s += len(l) - i
    while (i < len(l)):
        a[k] = l[i]
        i += 1
        k += 1
    while (j < len(r)):
        a[k] = r[j]
        j += 1
        k += 1
    return s
def main():
    while True:
        n = int(input())
        if n==0:
            return
        ll = list(map(int, input().split()))
        print(merge_sort(ll))
if __name__ == '__main__':
    main()
# 小木棍
描述
小明将一批等长的木棍随机切成最长为 50 单位的小段。现在他想要将木棍还原成原来的状态，但是却忘记了原来的木棍数量和长度。请写一个程序帮助他计算如果还原成原来的等长木棍，其长度可能的最小值。所有的长度均大于 0。
输入
输入包含多个实例。每个实例有两行，第一行是切割后的木棍数量 n（最多 64 个），第二行为 n 个以空格分开的整数，分别为每根木棍的长度。输入的最后以 n 为 0 结束。
输出
对于每个实例，输出一行其长度的可能的最小值。
样例输入
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
样例输出
6
5
来源
来自计算概论 B 期末考试，本题对数据进行了弱化
解决
N=105
a=[0 for _ in range(N)]
v=[0 for _ in range(N)]
target=0
n=0
maxn=0
def dfs(cnt, len, pos):
    if cnt == target:
        return True #拼够了根数，符合题意
    if len == maxn:
        return dfs(cnt+1, 0, 0) #拼完了一根 继续下一根
    i = pos
    while i<n:
        if v[i]==0 and len+a[i]<=maxn:
            v[i]=1
            if dfs(cnt, len+a[i], i):
                return True
            v[i]=0
            if len == 0:
                return False #凑第一根的时候可以随便选，如果随便选都凑不成一根，那这个长度不行 神奇剪枝！！
            while i+1<n and a[i+1]==a[i]:
                i += 1 #如果用当前的小木段拼凑 失败则与它等长的同样失败，小剪枝
        i += 1
    return False
while True:
    n=int(input())
    if n==0:
        break
    arr = input()
    a = [0 for _ in range(N)]
    a = [int(n) for n in arr.split()]
    asum = 0
    asum = sum(a)
    a=sorted(a,reverse=True)
    maxn = 0
    maxn=a[0]
    while maxn <= asum:
        if asum%maxn == 0:
            target = asum / maxn
            v = [0 for _ in range(N)]
            if dfs(0, 0, 0):
                break
        maxn += 1
    print(maxn)
# 修仙之路
描述
修仙之路长漫漫，逆水行舟，不进则退！你过五关斩六将，终于来到了仙界。仙界是一个 r 行 c 列的二维格子空间，每个单元格是一个” 境界 “，每个境界都有等级。你需要任意选择其中一个境界作为起点，从一个境界可以前往上下左右相邻四个境界之一 ，当且仅当新到达的境界等级增加。你苦苦行走，直到所在的境界等级比相邻四个境界的等级都要高为止，一览众山小。请问包括起始境界在内最长修仙路径需要经过的境界数是多少？
输入
第一行为两个正整数，分别为 r 和 c（1<=r,c<=100）。
接下来有 r 行，每行有 c 个 0 到 100000000 之间的整数，代表各境界的等级。
输出
输出一行，为最长修仙路径需要经过的境界数（包括起始境界）。
样例输入
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出
25
解决 1
没有考虑位于边界的 “仙境”
import java.util.Scanner;
/**]
 *
 * 5 5
 * 1 2 3 4 5
 * 16 17 18 19 6
 * 15 24 25 20 7
 * 14 23 22 21 8
 * 13 12 11 10 9
 *
 *
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int m= sc.nextInt();
        int n =sc.nextInt();
        int [][] nums = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j = 0;j<n;j++){
                nums[i][j] = sc.nextInt();
            }
        }
       /* int [][] dp = new int[m][n];
        dp[0][0] =1;
         int target =0;
        // i+1,j // i-1,j // i,j+1// i,j-1
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0){
                    continue;
                }
                if(i+1<m&&j<n && nums[i+1][j]<nums[i][j]){
                    dp [i][j] =Math.max(dp[i+1][j],dp[i][j])+1;
                }
                if (0<=i-1&&j<n&& nums[i-1][j]<nums[i][j]){
                    dp [i][j] =Math.max(dp[i-1][j],dp[i][j])+1;
                }
                 if(i<m&&j+1<n && nums[i][j+1]<nums[i][j]){
                    dp [i][j] =Math.max(dp[i][j+1],dp[i][j])+1;
                }
                if(i<m&&j-1>=0 && nums[i][j-1]<nums[i][j]){
                    dp [i][j] =Math.max(dp[i][j-1],dp[i][j])+1;
                }
                int tmp = nums[i][j];
                int tmp1 = dp[i][j];
                target = Math.max(dp[i][j],target);
            }
        }
        System.out.println(target);
*/
      int a = dfs(nums,0,0,m,n,1);
        System.out.println(a);
    }
    public static int  dfs(int [][] nums ,int i,int j ,int m, int n ,int tt ){
        if(i<0 || i>m || j<0||j>n){
            return 0;
        }
        if(is(nums,i,j,m,n)==4){
           return tt;
        }
        int a =0;
        int b=0;
        int c=0;
        int d=0;
        if(i-1>=0&&nums[i][j]<nums[i-1][j]){
            a= dfs(nums, i-1, j, m, n,tt+1);
        }
         if(i+1<m&&nums[i][j]<nums[i+1][j]){
            b= dfs(nums, i+1, j, m, n,tt+1);
        }
         if(j-1>=0&&nums[i][j]<nums[i][j-1]){
            c= dfs(nums, i, j-1, m, n,tt+1);
        }
         if(j+1<n&&nums[i][j]<nums[i][j+1]){
            d= dfs(nums, i, j+1, m, n,tt+1);
        }
         a= Math.max(a,b);
         a= Math.max(a,c);
         a= Math.max(a,d);
        return  a;
    }
    public static int is(int [][] nums,int i,int j,int m,int n){
        int tar=0;
        if(i-1>=0){
            if( nums[i][j]>nums[i-1][j]){
               tar++;
            }
        }
        if(i+1<m){
            if( nums[i][j]>nums[i+1][j]){
                tar++;
            }
        }
        if(j-1>=0){
            if( nums[i][j]>nums[i][j-1]){
                tar++;
            }
        }
        if(j+1<n){
            if( nums[i][j]>nums[i][j+1]){
                tar++;
            }
        }
        return  tar;
    }
}
来自啊鱼咕嘟
解决 2
# 5 5
# 1 2 3 4 5
# 16 17 18 19 6
# 15 24 25 20 7
# 14 23 22 21 8
# 13 12 11 10 9
n,m=map(int,input().split())
nums = []
for _ in range(n):
	nums.append(list(map(int, input().split())))
dp=[[-1]* m for _ in range(n)]
move=[[0,1],[1,0],[-1,0],[0,-1]]
def dfs(i,j):
    if dp[i][j]!=-1:
        return dp[i][j]
    ret=1
    for oi,oj in move:
        ni,nj=i+oi,j+oj
        if 0<=ni<n and 0<=nj<m and nums[i][j]>nums[ni][nj]:
            ret=max(ret,dfs(ni,nj)+1)
    dp[i][j]=ret
    return dp[i][j]
res=0
for i in range(n):
    for j in range(m):
        res=max(res,dfs(i,j))
print(res)
# 拦截导弹
描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数），计算这套系统最多能拦截多少导弹。
输入
第一行是一个整数 N（不超过 15），表示导弹数。
第二行包含 N 个整数，为导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数）。
输出
一个整数，表示最多能拦截的导弹数。
样例输入
8
389 207 155 300 299 170 158 65
样例输出
6
解决
i=0
data = [0 for _ in range(100)]
ans = [0 for _ in range(100)]
n=int(input())
arr=input()
data = [int(n) for n in arr.split()]
ans[0] = 1
maxt = 1
for j in range(1, n):
    ans[j] = 1
    for i in range(0, j):
        if data[i]>=data[j]:
            if ans[i]+1> ans[j]:
                ans[j] = ans[i]+1
    if ans[j]> maxt:
        maxt = ans[j]
print(maxt)
# 采药（DP）
描述
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入
输入的第一行有两个整数 T（1 <= T <= 1000）和 M（1 <= M <= 100），T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
来源
NOIP 2005
解决
N=1010
T,M=map(int,input().split())
f = [0 for _ in range(N)]
for i in range(0, M):
        v,w=map(int,input().split())
        for j in range(T, v - 1, -1):
            f[j] = max(f[j], f[j - v] + w)
print(f[T])
# 简单的整数划分问题
描述
将正整数 n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中 n1>=n2>=…>=nk>=1 ，k>=1 。
正整数 n 的这种表示称为正整数 n 的划分。正整数 n 的不同的划分个数称为正整数 n 的划分数。
输入
标准的输入包含若干组测试数据。每组测试数据是一个整数 N (0 < N <= 50)。
输出
对于每组测试数据，输出 N 的划分数。
样例输入
5
样例输出
7
提示
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
解决
def f(x,y):
        if y == 1:
            return 1
        elif y <= 0:
            return 0
        elif x < y:
            return 0
        else:
            return(f(x - 1,y - 1) + f(x - y,y))
while True:
    try:
        n = int(input())
        s = 1
        for i in range(n):
            s = s + f(n,i)
        print(s)
    except EOFError: break
       
 更新於   閱讀次數  次
請我喝[茶]~(￣▽￣)~*
fygod 微信支付
微信支付
fygod 支付寶
支付寶
fygod PayPal
PayPal