小米9.19笔试

第一题dp，第一次卡在中间dp过程要取最大值，第二次卡在数组大小宽度要设置成1000
```c++
#include
#include
#include
#include
using namespace std;
int main()
{
    int t;
cin>>t;
    const int N = 505;
    const int B = 1005;
    while (t--)
    {

        int arr[N];
        int box,num,single;
cin>>box>>num>>single;
        for(int i =1;i<=num;i++)
        {
cin>>arr[i];
        }
if(single>=box)
        {
            cout<<"YES"<            continue;
        }
        //cal
        bool dp[N][B];
        for(int i = 0;i        dp[0][i]=0;
        //只有num个物品
        //dp[a][b]表示选择装了前a个东西能塞满b个空间
        //2 3 5 7
        //dp[0][...]=0
        //dp[1][01]=0,dp[1][2]=1,dp[1][3]...=0
        //dp[2][01]=dp[01],dp[2][2]=1,dp[2][3]=1,dp[2][4]=0(从dp[1][1]转移过来,为0)dp[2][5]=1()
        for(int i = 1;i<=num;i++)
        {
            for(int j = 0;j            {
                //如果放不下，就复制
                //放得下,dp[i][j]=dp[i-1][j-arr[i]]
if(arr[i]>j)dp[i][j]=dp[i-1][j];
                else if(arr[i]==j) dp[i][j]=1;
                else if(arr[i]                //要么放进去，要么不放进去
                dp[i][j]=max(dp[i-1][j-arr[i]],dp[i-1][j]);

            }
        }
        bool res=false;
        //只要满足[box-single,box]的区间就能装满
for(int i = box;i>=box-single;i--)
        {
            if(dp[num][i]==true)res=true;
        }
        if(res)cout<<"YES"<        else cout<<"NO"<    }


    return 0;
}
```
第二题贪心，每一次往前看的时候如果是升序序列就选符合条件下尽量小的，反之亦然
```c++
#include
#include
#include
#include
using namespace std;
const int N = 1e5+10;
int arr[N];
int brr[N];

int main()
{
    int n;
cin>>n;
    while(n--)
    {
        int size;
cin>>size;
        for(int i=0;i        {
            scanf("%d",&arr[i]);
        }
        for(int i=0;i        {
            scanf("%d",&brr[i]);
        }
        int res1=true;
        //升序和降序都试一次，每一次选择符合条件的且
        //升序的时候更小的，降序的时候更大的
        int cur =0;
        cur = min(arr[0],brr[0]);
        for(int i = 1;i        {
            int a = arr[i];
            int b = brr[i];
if(a>=cur && b>=cur)
            {
                cur = min(a,b);
            }
            else if(a            {
                res1 = false;
                break;
            }
            else
            {
                cur = max(a,b);
            }
        }
        bool res2=true;
        int cur2 =0;
        cur2 = max(arr[0],brr[0]);
        for(int i = 1;i        {
            int a = arr[i];
            int b = brr[i];
            if(a<=cur2 && b<=cur2)
            {
                cur2 = max(a,b);
            }
else if(a>cur2 && b>cur2)
            {
                res2 = false;
                break;
            }
            else
            {
                cur2 = min(a,b);
            }
        }
        if(res1||res2)cout<<"YES"<        else cout<<"NO"<
    }

    return 0;
}
```

小米9.19笔试

全站热榜