dp-淘宝的推荐系统

野性酷女 2023-07-18 02:24 85阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 1]

//过不了
    import java.util.Scanner;
    
    public class Main {
        
        static int maxn=100003;
        static int tt,x,n,m,ans;
        static int[]f;
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            int tt=scanner.nextInt();
            while(tt>0) {
        
                f=new int[maxn];
                tt--;
                ans=0;
                n=scanner.nextInt();
                m=scanner.nextInt();
                int nn=0;
                for (int i = 1; i <=n; i++) {
        
                    x=scanner.nextInt();
                    int w=f[x]+1;
                    for (int j = Math.max(1, x-m); j <=Math.min(maxn-1, x+m); j++) {
        
                        f[j]=Math.max(f[j], w);
                        nn++;
                    }
                }
                for (int i = 1; i < nn; i++) {
        
                    ans=Math.max(ans, f[i]);
                }
                System.out.println(ans);
            }
    
        }
    }

# AC #

import java.util.Scanner;
    
    public class Main {
        
        static int n,d;
        static int a[];
        static int dp[];
        static int mm[];
        public static int fn(int x){
        
            int ans=0;
            for (int i = Math.max(a[x]-d,0); i <=Math.min(a[x]+d,100000) ; i++) {
        
                ans=Math.max(ans,mm[i]);
            }
            return ans;
        }
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            int t=scanner.nextInt();
            while (t>0){
        
                a=new int[300005];
                dp=new int[300005];
                mm=new int[200005];
                t--;
                n=scanner.nextInt();
                d=scanner.nextInt();
                for (int i = 1; i <=n ; i++) {
        
                    a[i]=scanner.nextInt();
                }
                for (int i = 1; i <=n ; i++) {
        
                    dp[i]=fn(i)+1;
                    mm[a[i]]=dp[i];//记录序号和价格
                }
                int ans=0;
                for (int i = 1; i <=n ; i++) {
        
                    ans=Math.max(ans,dp[i]);
                }
                System.out.println(ans);
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020032313072342.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 1]: /images/20230528/bbd5a296b1114e2a867d10fd74ffc160.png